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

using namespace std;

#define MAX_K	1000010
#define MAX_M	1000010

int N, M, o, mo, p, s, mS, dP, dV, t;
long long mZ, z;
vector<int> k, l;
vector<deque<int>> mP;
char c[MAX_M];

int gcd(int a, int b) {
        if (a < b) {
                swap(a, b);
        }

        while (b != 0) {
                t = a % b;
                a = b;
                b = t;
        }

        return a;
}

int gmp(int v) {
	return mP[2 * mo + v + dV].front() + dP;
}

int main()
{
	scanf("%d", &N);
	k.resize(N);
	for (int i = 0; i < N; i++) {
		scanf("%d", &k[i]);
	}
	scanf("%d", &M);
	scanf("%s", c);

	l.resize(M);
	for (int i = M; i < N; i++) {
		p = i % M;
		if (k[i] < k[p]) {
			k[p] = k[i];
			l[p] = i - p;
		}
	}

	o = gcd(M, N);
	mo = M / o;

	mZ = -1LL;
	for (int i = 0; i < o; i++) {
		s = mS = 0;
		mP.clear(); mP.resize(4 * mo + 1);

		for (int j = 0, p = i; j < mo; j++, p = (p + N) % M) {
			s += c[p] == 'W' ? -1 : 1;
			mP[2 * mo + s].push_back(j);
			if (s > mS) {
				mS = s;
			}
		}
		for (int j = 0, p = i; j < mo; j++, p = (p + N) % M) {
			s += c[p] == 'W' ? -1 : 1;
			mP[2 * mo + s].push_back(mo + j);
		}
		s = s / 2;

		dP = dV = 0;
		for (int j = 0, p = i; j < mo; j++, p = (p + N) % M) {
			if (p < N) {
				if (k[p] <= mS) {
					z = 1LL * gmp(k[p]) * N + 1LL * (l[p] + p + 1);
					if (mZ == -1LL || z < mZ) {
						mZ = z;
					}
				} else if (s > 0) {
					t = (k[p] - mS) / s;
					if (t * s < k[p] - mS) {
						t++;
					}
					z = 1LL * t * N * mo + 1LL * gmp(k[p] - t * s) * N + 1LL * (l[p] + p + 1);
					if (mZ == -1LL || z < mZ) {
						mZ = z;
					}
				}
			}

			dP--;
			mP[2 * mo + dP].pop_front();
			if (c[p] == 'W') {
				dV--;
				mS++;
			} else {
				dV++;
				if (mS > s) {
					mS--;
				}
			}
		}
	}

	printf("%lld\n", mZ);
	return 0;
}