1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
#include<bits/stdc++.h>
using namespace std;
#define REP(i, n) for(int i = 0; i < (n); i++)
#define SIZE(s) ((int) (s).size())
#define SCAND(x) assert(scanf("%d", x) == 1)
#define SCANS(x) assert(scanf("%s", x) == 1)
#define ALL(s) s.begin(), s.end()
#define MP make_pair
#define ST first
#define ND second
#define VAR(x) if(0) cout << #x << " = " << x << endl
using LL = long long;
using PII = pair<int, int>;

const int N = 1e6;
const int M = 1e6;

int n;
int cash[N];
int m;
char w[M+1];

int minint(int a, int b){return min(a, b);}

struct event {
  int i; // where to put result
  int r; // value we look for
  event(int i, int r):i(i),r(r){}
};

struct query {
  int i; // guy index (to access cash[i])
  int x; // x of first occurrence in graph
  query(int i, int x):i(i),x(x){}
};

struct cyclic {
  cyclic(vector<int> ds):k(ds.size()), fs(k + 1), pm(k), sm(k){
    partial_sum(ALL(ds), fs.begin() + 1);
    partial_sum(fs.begin(), fs.end() - 1, pm.begin(), minint);
    partial_sum(fs.rbegin() + 1, fs.rend(), sm.rbegin(), minint);
  }
  vector<LL> solve(vector<query> qs){
    vector<vector<event>> events(k);
    vector<LL> result(qs.size());
    int d = fs[0] - fs.back();
    int minval = min(sm[0] - d, sm[0]);
    REP(i, SIZE(qs)){
      int x = qs[i].x;
      int s = cash[qs[i].i];
      int l = max(fs[x] - sm[x], fs[x] - fs.back() + fs[0] - pm[x]);
      int t;
      if(l > s) t = 0;
      else if(d <= 0) t = -1;
      else t = (s-l+d-1)/d;
      if(t != -1){
        result[i] = qs[i].i + ((LL) t * k - 1) * n;
        events[x].emplace_back(i, fs[x] - s + d * t);
      } else {
        result[i] = -1;
      }
    }
    vector<vector<int>> listeners(2*k);
    REP(i, k){
      for(event e : events[i])
        listeners[e.r - minval].push_back(e.i);
      for(int li : listeners[fs[i] - minval]) 
        result[li] += (LL) n * (i - qs[li].x);
      listeners[fs[i] - minval].clear();
    }
    REP(i, k){
      for(int li : listeners[fs[i] - d - minval])
        result[li] += (LL) n * (i + k - qs[li].x);
      listeners[fs[i] - d - minval].clear();
    }
    return result;
  }
  int k;
  vector<int> fs;
  vector<int> pm;
  vector<int> sm;
};

vector<cyclic> cyclics;
vector<vector<query>> qss;
int cidx[M];


void makecyclic(int begin){
  vector<int> ds;
  for(int i = begin; ds.empty() || i != begin; i = (i + n) % m){
    cidx[i] = ds.size();
    if(w[i] == 'P') ds.push_back(-1);
    else if(w[i] == 'W') ds.push_back(+1);
    else assert(0);
  }
  cyclics.emplace_back(ds);
}

int main(){
  SCAND(&n);
  REP(i, n) SCAND(&cash[i]);
  SCAND(&m);
  SCANS(w);
  assert((int) strlen(w) == m);
  int c = __gcd(n, m);
  REP(i, c) makecyclic(i);
  qss.resize(c);
  REP(i, n){
    qss[i%cyclics.size()].emplace_back(i, cidx[i%m]);
  }
  LL result = 0;
  REP(i, c){
    vector<LL> v = cyclics[i].solve(qss[i]); 
    for(LL ll : v) if(ll != -1){
      if(result == 0) result = ll;
      else result = min(result, ll);
    }
  }
  printf("%lld\n", (result == 0) ? -1 : result+1);
}