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
124
125
#include <cstdio>
#include <vector>
#include <map>
#include <algorithm>
#include <cassert>
#define ll long long
#define INF 1000000000000000001LL
using namespace std;

int a[1000000];
char cm[1000001];
struct {int cykl,pos,valpos,minto,minfrom;} cb[1000000];
struct cykl{int r,wm,pm,len; map<int,vector<int> > pozycje;
	cykl():r(0),wm(1000001),pm(0),len(0) {}
};
vector<cykl> C;

void brut(int n, int m, char *cm) {
	vector<int> b; b.resize(n);
	for (int i=0;i<n;i++) b[i]=a[i];
	ll ile=0;
	int g=0,p=0;
	while(1) {
		ile++;
		b[g] += (cm[p]=='W'?1:-1);
		if (b[g]==0) break;
		//else //printf("%d ",b[g]);
		g=(g+1)%n;
		p=(p+1)%m;
	}
	printf("brut: %lld  g=%d  p=%d\n",ile,g,p);
}

void rozklad(int n, int m, char *cm) {
	int cn=0;
	C.push_back(cykl());
	for (int i=0;i<m;i++) {
		if (cb[i].cykl==0) {
			cn++; C.push_back(cykl());
			int j=i,p=0;
			while (cb[j].cykl==0) {
				cb[j].cykl=cn;
				cb[j].valpos=C[cn].r;
				C[cn].r += (cm[j]=='W'?1:-1);
				C[cn].pozycje[C[cn].r].push_back(p);
				if (C[cn].r<C[cn].wm) {
					C[cn].wm=C[cn].r;
					C[cn].pm=p;
				}
				cb[j].minto=C[cn].wm;
				cb[j].pos=p++;
				j = (j+n)%m;
			}
			C[cn].len=p;
			j=j-n; if (j<0) j+=m;
			int wm=cb[j].valpos;
		}
	}
	for (int i=1;i<C.size();i++) {
		//printf("cykl=%d len=%d r=%d wm=%d pm=%d\n",i,C[i].len,C[i].r,C[i].wm,C[i].pm);
		for (map<int,vector<int> >::iterator p=C[i].pozycje.begin();p!=C[i].pozycje.end();p++) {
			//printf("%d: ",p->first);
			for (int j=0;j<p->second.size();j++);
				//printf("%d ",p->second[j]);
		}
		//printf("");
	}
	
	for (int i=0;i<m;i++); //printf("l=%d cykl=%d pos=%d valpos=%d\n",i,cb[i].cykl,cb[i].pos,cb[i].valpos);
}

int main() {
	int n;
	scanf("%d",&n);
	for (int i=0;i<n;i++) scanf("%d",&a[i]);
	int m;
	scanf("%d\n",&m);
	gets(cm);
	//brut(n,m,cm);
	rozklad(n,m,cm);
	ll best=INF;int bestgn;
	for (int i=0;i<n;i++) {
		int pocz = i%m;
		cykl &cy = C[cb[pocz].cykl];
		int pos = cb[pocz].pos;
		int spad = cb[pocz].valpos-cy.wm; 
		int spadpo = cy.pm-pos+1; if (spadpo<0) spadpo+=cy.len;
		//printf("spad=%d po %d  ",spad,spadpo);
		ll dozera;
		if (spad>=a[i]) {
			int d = cb[pocz].valpos-a[i];
			//printf("d=%d\n",d);
			vector<int> &v = cy.pozycje[d];
			assert(v.size()>0);
			vector<int>::iterator it = lower_bound(v.begin(),v.end(),pos);
			if (it!=v.end()) 
				dozera=*it-pos;
			else
				dozera=pos-*v.begin()+cy.len;
		} else if (cy.r>=0)
			dozera=INF;
		else {
			ll ilec=((a[i]-spad-1)/(-cy.r)+1);
			dozera = ilec*cy.len;
			int d = cb[pocz].valpos-(a[i]+ilec*cy.r);
			//printf("d=%d\n",d);
			vector<int> &v = cy.pozycje[d];
			vector<int>::iterator it = lower_bound(v.begin(),v.end(),pos);
			if (it!=v.end()) 
				dozera+=*it-pos;
			else
				dozera+=pos-*v.begin()+cy.len;
		}
		
		//printf("gracz %d dozera po %lld\n",i,dozera+1);
		if (dozera<best) {best=dozera; bestgn=i;}
	}
	if (best==INF)
		printf("-1\n");
	else {
		ll ans=(best)*n+bestgn+1;
		printf("%lld\n",ans);
	}
	return 0;
}