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

using namespace std;

typedef long long ll;
typedef pair<ll,int> plli;

// struct three { 
// 	int index, quot, rem; 
// 	three(int _index, int _quot, int _rem) 
// 		: index(_index), quot(_quot), rem(_rem) { }
// };

vector<int> budget, cycle_vals;
deque<int> Q, emptyQ;
priority_queue<plli, vector<plli>, greater<plli> > finals;

char cycle_string[1000001];

int change_in_cycle;

int main() {

	ll n;
	scanf("%lld", &n);

	// change_in_cycle.resize(n);
	budget.resize(n);
	cycle_vals.resize(n);

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

	ll m;
	scanf("%lld", &m);
	scanf("%s", cycle_string);

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

	// count change in cycle

	// change_in_cycle = cycle_vals[0];
	// for(int i = (n >= m ? n-m : n);; i += n) {
	// 	while(i >= m) i -= m;
	// 	if(i == 0) break;
	// 	change_in_cycle += cycle_vals[i];
	// }
	for(int i = 0; i < m; i++)
		change_in_cycle += cycle_vals[i];

	// printf("before-1\n");
	if(change_in_cycle >= 0) {
		printf("-1");
		return 0;
	}
	// printf("after-1\n");

	// printf("change_in_cycle: %d\n", change_in_cycle);

	int min_cycle_count = 1073741824;
	for(int i = 0; i < n; i++) {
		div_t d = div(budget[i], -change_in_cycle);
		if(d.quot <= min_cycle_count) {
			if(d.quot < min_cycle_count) Q = emptyQ;
			min_cycle_count = d.quot;
			if(d.rem == 0) Q.push_front(i);
			else Q.push_back(i);
		}
	}
	min_cycle_count++;

	// printf("min_cycle_count: %d\n", min_cycle_count);

	while(!Q.empty()) {

		int curr = Q.front();
		Q.pop_front();

		// printf("budget[%d] %d\tmin_cycle_count %d\tchange_in_cycle %d\n", curr, budget[curr], min_cycle_count, change_in_cycle);

		int bdgt = budget[curr] + min_cycle_count*change_in_cycle;
		ll	ttime = (ll)curr + ((ll)min_cycle_count)*n,
			counter = ttime % m;

		// printf("curr %d\tbdgt %d\tttime %lld\tcounter %lld\n", curr+1, bdgt, ttime, counter);

		while(bdgt > 0) {
			counter++;
			ttime += n;
			while(counter >= m) counter -= m;
			// printf("\tttime %lld\tcounter %lld\n", ttime, counter);
			bdgt += cycle_vals[counter];
		}

		finals.push(plli(ttime, curr));
		// printf("\n\n");

	}

	// printf("before\n");
	// if(!finals.empty()) printf("%d %d", finals.top().first+1, finals.top().second+1);
	if(!finals.empty()) printf("%lld", finals.top().first+1LL);
	else printf("-1");
	// printf("after\n");
	//   ^^^^^^^^^^^^^ just in case

	return 0;
}