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
#include <iostream>
#include <vector>
using namespace std;

const long long NIE = 2000000000000000000LL;

long long p[1000010], r[1000010];
vector <long long> rp[1000010];
vector <long long> s[2000010];
long long mn[1000010];
long long sm[1000010];

long long policz(long long x, long long n, long long m) {
	vector <long long> cykl;
	long long suma = 0;
	x = x % m;
	cykl.push_back(x);
	suma += r[x];
	for(long long i = (x + n) % m; i != x; i = (i + n) % m) {
		cykl.push_back(i);
		suma += r[i];
	}
	long long sum2 = 2 * suma;
	long long amn = 2000000, awm = -2000000, d = 1000000;
	for(long long i = cykl.size() - 1; i >= 0; i --) {
		sum2 -= r[cykl[i]];
		s[sum2 + d].push_back(i + cykl.size());
		amn = min(amn, sum2);
	}
	for(long long i = cykl.size() - 1; i >= 0; i --) {
		sum2 -= r[cykl[i]];
		amn = min(amn, sum2);
		mn[i] = amn;
		sm[i] = sum2;
		s[sum2 + d].push_back(i);
	}
	long long w = NIE, aw, k;
	for(long long i = 0; i < cykl.size(); i ++) {
		for(long long j = 0; j < rp[cykl[i]].size(); j ++) {
			long long y = rp[cykl[i]][j];
			if(p[y] + mn[i] - sm[i] <= 0) {
				aw = y + (s[sm[i] - p[y] + d].back() - i) * n - n + 1;
				w = min(w, aw);
			}
			else if(suma < 0) {
				k = (p[y] + mn[i] - sm[i] - 1) / (-1 * suma) + 1;
				p[y] += k * suma;
				aw = y + (s[sm[i] - p[y] + d].back() - i) * n + cykl.size() * n * k - n + 1;
				w = min(w, aw);
			}
			p[y] = 0;
		}
		s[sm[i] + d].pop_back();
	}
	for(int i = amn; i <= awm; i ++) {
		s[i].clear();
	}
	return w;
}

int main() {
	ios_base::sync_with_stdio(0);
	long long n, m;
	char c;
	cin >> n;
	for(long long i = 0; i < n; i ++) {
		cin >> p[i];
	}
	cin >> m;
	for(long long i = 0; i < m; i ++) {
		cin >> c;
		if(c == 'W') {
			r[i] = 1;
		}
		else {
			r[i] = -1;
		}
	}
	for(long long i = 0; i < n; i ++) {
		rp[i % m].push_back(i);
	}
	long long wyn = NIE;
	for(long long i = 0; i < n && p[i]; i ++) {\
		wyn = min(wyn, policz(i, n, m));
	}
	if(wyn != NIE) {
		cout << wyn;
	}
	else {
		cout << -1;
	}
	cout << endl;
}