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
122
123
124
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <vector>
#include <map>
#include <queue>
#include <set>

using namespace std;

const int N = 1000010;

int A[N];
int B[N];
char S[N];

int P[N+N];
int PS[N+N];

vector<pair<int,pair<int,int> > > V;
vector<pair<int,int> > VS;
vector<pair<int,int> > IVS;

set<pair<int, int> > SS;
set<pair<int, int> > ISS;



int gcd(int a, int b) {
    return b == 0 ? a : gcd(b,a%b);
}

int main()
{
    int n;
    scanf("%d",&n);
    for(int i=0;i<n;++i)
        scanf("%d",&A[i]);
    int m;
    scanf("%d",&m);
    scanf("%s",S);

    int G=gcd(n,m);
    int lm=m/G;
    long long ret = 1000000000000000000LL;
    for(int i=0;i<G;++i) {
        int w=i;
        for(int j=0;j<lm;++j) {
            B[w]=j;
            P[j]=P[j+lm]=(S[w]=='P' ? 1: -1);
            w+=n;
            w%=m;
        }
        PS[0]=P[0];
        for(int j=1;j<lm+lm;++j)
            PS[j]=PS[j-1]+P[j];

        V.clear();
        for(int j=i;j<n;j+=G) {
            V.push_back(make_pair(B[j%m],make_pair(A[j],j)));
        }
        sort(V.begin(), V.end());

        SS.clear();
        ISS.clear();
        VS.clear();
        IVS.clear();
        for(int j=0;j<lm;++j) {
            pair<int,int> pii = make_pair(PS[j],j);
            VS.push_back(pii);
            SS.insert(pii);
            pair<int,int> ipii = make_pair(-PS[j],j);
            ISS.insert(ipii);
            IVS.push_back(ipii);
        }

        int ab=0;
        int cr=0;
        int r=PS[lm-1];
        for(int j=0;j<V.size();++j) {
            int f1=V[j].first;
            int f2=V[j].second.first;
            int f3=V[j].second.second;
            while(f1>ab) {
                SS.erase(VS[ab]);
                ISS.erase(IVS[ab]);
                if (P[ab]==1) --cr; else ++cr;
                pair<int,int> pii = make_pair(PS[ab+lm-1]+P[ab+lm],ab+lm);
                pair<int,int> ipii = make_pair(-(PS[ab+lm-1]+P[ab+lm]),ab+lm);
                ab++;
                VS.push_back(pii);
                SS.insert(pii);
                IVS.push_back(ipii);
                ISS.insert(ipii);
            }
            set<pair<int,int> >::iterator it=SS.upper_bound(make_pair(f2-cr,-1));
            if (it!=SS.end()) {
                int ind=(*it).second;
                long long ta=ind-ab;
                ret=min(ret,f3+ta*n);
            } else {
                if (r<=0) continue;
                set<pair<int,int> >::iterator it2 = ISS.lower_bound(make_pair(-1000000000,0));
                int mxx=(-(*it2).first)+cr;
                long long cyc=(f2-mxx)/r;
                f2 -= cyc*r;
                if (f2>mxx) {
                    f2-=r;
                    ++cyc;
                }
                it=SS.upper_bound(make_pair(f2-cr, -1));
                int ind=(*it).second;
                long long ta = ind-ab;
                ret=min(ret, f3+(n)*(lm*cyc+ta));
            }
        }
    }
    if (ret==1000000000000000000LL)
        printf("-1\n");
    else
        printf("%lld\n",ret+1);

    return 0;
}