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
#include <iostream>
#include <stdio.h>

using namespace std;

const int GL = 21;

int d[1000000];
int war[1000000];
int kt2[GL][1000000];
int sum2[GL][1000000];
int mini2[GL][1000000];
int n, m;

pair<int, int> get_mini(int pos, int len) {
	len--;
	int cur_sum = war[pos];
	int cur_mini = min(0, cur_sum);
	int cur_pos = pos;
	for (int i = 0; i < GL; i++) {
		if (len & 1) {
			cur_sum -= war[cur_pos];
			cur_mini = min(cur_mini, cur_sum + mini2[i][cur_pos]);
			cur_sum += sum2[i][cur_pos];
			cur_pos = ((1ll << i) * (long long) n + cur_pos) % m;
		}
		len >>= 1;
	}
	return make_pair(cur_mini, cur_sum);
}

int get_mini_first(int pos, int len) {
	len--;
	int cur_sum = war[pos];
	int cur_mini = min(0, cur_sum);
	int cur_pos = pos;
	for (int i = 0; i < GL; i++) {
		if (len & 1) {
			cur_sum -= war[cur_pos];
			cur_mini = min(cur_mini, cur_sum + mini2[i][cur_pos]);
			cur_sum += sum2[i][cur_pos];
			cur_pos = ((1ll << i) * (long long) n + cur_pos) % m;
		}
		len >>= 1;
	}
	return cur_mini;
}

long long min_res = 9223372036854775807ll;

long long bin_search(const int pos) {
	const int posm = pos % m;
	pair<int, int> cykl = get_mini(posm, m);
	if (cykl.first + d[pos] > 0 && cykl.second >= 0) return 99999999999999ll;
	long long iCykli = 0;
	if (cykl.first + d[pos] > 0) {
		iCykli = max(0ll, ((long long)cykl.first + (long long)d[pos] - 1) / ((long long)-cykl.second) + 1);
		d[pos] += (long long)iCykli * (long long)cykl.second; 
	}	
	if ((long long)iCykli * (long long)m * (long long) n + (long long) pos + 1 > min_res) return (long long)iCykli * (long long)m;
	int imin = 1;
	int imax = 1000005ll;
	while (imin < imax)
    {
      int imid = (imin + imax) / 2;
      if (get_mini_first(posm, imid) + d[pos] > 0)
        imin = imid + 1;
      else
        imax = imid;
    }
    return imax - 1 + (long long)iCykli * (long long)m;
}

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

	scanf("%d", &m);

	char ciag[m + 1];
	scanf("%s", ciag);

	for (int i = 0; i < m; i++) war[i] = (ciag[i] == 'W' ? 1 : -1);

	for (int i = 0; i < m; i++) {
		kt2[0][i] = (i + n) % m;
	}
	for (int j = 1; j < GL; j++) {
		for (int i = 0; i < m; i++) {
			kt2[j][i] = kt2[j - 1][kt2[j - 1][i]];
		}
	}

	for (int i = 0; i < m; i++) {
		sum2[0][i] = war[i] + war[kt2[0][i]];
	}
	for (int j = 1; j < GL; j++) {
		for (int i = 0; i < m; i++) {
			sum2[j][i] = sum2[j - 1][i] + sum2[j - 1][kt2[j - 1][i]] - war[kt2[j - 1][i]];
		}
	}

	for (int i = 0; i < m; i++) {
		mini2[0][i] = min(0, min(war[i], war[i] + war[kt2[0][i]]));
	}
	for (int j = 1; j < GL; j++) {
		for (int i = 0; i < m; i++) {
			mini2[j][i] = min(mini2[j - 1][i], mini2[j - 1][kt2[j - 1][i]] + sum2[j - 1][i] - war[kt2[j - 1][i]]);
		}
	}

	// 9999999999999
	for (int i = 0; i < n; i++) {
		long long b_s = bin_search(i);
		if (b_s != 99999999999999) min_res = min(min_res, b_s * (long long) n + (long long) i + 1);
	}
	if (min_res == 9223372036854775807ll) {
		printf("-1");
	} else {
		printf("%lld\n", min_res);
	}
	return 0;
}