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
#include <cstdio>
#include <vector>
#include <algorithm>

using namespace std;

char _A[1000006];
char A[1000006];
int _M[1000006];
int M[1000006];
int _S[2000006];
int PP[1000006];

class {
    public:
        int A[ 5000006 ];
        int size;
        void setup( int *tab, int n ) {
            size=2;
            while ( size<n ) size*=2;
            for ( int i=0; i<n; i++ ) A[size+i]=tab[i];
            for ( int i=size+n; i<=2*size; i++ ) A[i]=-3000006;
            for ( int i=size-1; i>0; i-- )
                A[i]=max(A[2*i],A[2*i+1]);
            A[0]=-3000006;
        }
        int mx( int b, int e ) {
            b+=size; e+=size;
            int r = max( A[b], A[e] );
            while (b/2<e/2) {
                if (!(b&1)) r=max(r,A[b+1]);
                if (  e&1 ) r=max(r,A[e-1]);
                b>>=1; e>>=1;
            }
            return r;
        }
        int find_next( int b, int v ) {
            b += size;
            if ( A[b] >= v ) return b-size;
            while ( 1 ) {
                if ( !(b&1) && A[b+1]>=v ) {
                    b++; break;
                }
                b>>=1;
            }
            while ( b<size ) {
                b<<=1;
                if ( A[b]<v ) b++;
            }
            return b-size;
        }
} T;

long long process( int n, int m ) {
    long long w = 3e18;
    int p = 0;
    int s = 0;
    _S[0]=0; int *S=_S+1;
    for ( int i=0; i<2*m; i++ ) {
        if ( A[p] == 'W' ) s--; else s++;
        S[i]=s;
        if ( i<m ) PP[p]=i;
        p=(p+n)%m;
    }
    T.setup( S, 2*m );
    for ( int _i=0; _i<n; _i++ ) {
        int mm = M[_i];
        int i=PP[_i%m];
        int mx = T.mx(i,i+m-1)-S[i-1];
        int s = S[i+m-1]-S[i-1];
        if ( mx <= 0 ) continue;
        int a = 0;
        if ( s > 0 ) {
            a = max( 0, (mm-mx+s-1)/s );
            mm -= a*s;
        }
        if ( mm > mx ) continue;
        long long _w = ((long long)a)*m;
        if ( mm ) {
           int aa = T.find_next( i, mm+S[i-1] )-i;
           _w += aa;
        }
        w=min( w, _w*n+_i );
    }
    return w;
}

int nwd( int a, int b ) {
    if (a&&b) return nwd(b,a%b);
    return a+b;
}

int main() {
    /*int AA[] = { 1,2,3,12,5 };
    T.setup( AA, 5 );
    printf("%d\n",T.find_next(1,4));
    return 0;// */
    int n,m;
    scanf("%d",&n);
    for ( int i=0; i<n; i++ )
        scanf("%d",_M+i);
    scanf("%d",&m);
    scanf("%s",_A);
    int dz = nwd( n, m );
    //if (dz!=1) printf("%d ",dz); //return 0;
    long long w = 3e18;
    for ( int i=0; i<dz; i++ ) {
        for ( int j=i; j<n; j+=dz ) M[j/dz]=_M[j];
        for ( int j=i; j<m; j+=dz ) A[j/dz]=_A[j];
        long long _w = process( n/dz, m/dz );
        if ( _w != 3e18 )
           w = min( w, _w*dz+i+1 );
    }
    if ( w == 3e18 ) printf("-1\n");
          else printf("%lld\n",w); 
    return 0;
}