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
#include<bits/stdc++.h>
using namespace std;

typedef long long int ll;

int twe[1000009],twy[1000009];
pair<int,int> td[4200007];
int N;
list<int> lista;

int nwd(int a, int b)
{
	while(a>0 && b>0)
		if(a>b) a%=b; else b%=a;
	return a+b;
}


void Init(int n)
{
	for(N=1;N<=n;N<<=1);
																		//printf("%d %d\n",n,N);
	for(int i=0;i<N<<1;++i) td[i]=make_pair(1e9,1e9);
}

void Insert(int pos, int v)
{
	pos+=N;
	td[pos].first=v;
	td[pos].second=v;
	pos>>=1;
	while(pos>0)
	{
		td[pos].first=min(td[pos<<1].first,td[(pos<<1)+1].first);
		td[pos].second=max(td[pos<<1].second,td[(pos<<1)+1].second);
		pos>>=1;
	}
}

int Query(int p, int v)
{
	int ak=1,pocz=0,kon=N-1;
	while(ak<N)
	{
																		//printf("%d %d %d %d\n",ak,v,td[ak*2].first,td[ak*2].second);
		if((pocz+kon)>>1>=p && td[ak*2].first<=v && td[ak*2].second>=v)
		{
			ak<<=1;
			kon=(pocz+kon)>>1;
		}
		else
		{
			ak=ak*2+1;
			pocz=(pocz+kon)/2+1;
		}
	}
	return ak-N;
}

int Qmin(int p, int k, int ak=1, int pocz=0, int kon=N-1)
{
	if(pocz>k || kon<p) return 1e9;
	if(pocz>=p && kon<=k) return td[ak].first;
	return min(Qmin(p,k,ak<<1,pocz,(pocz+kon)>>1),Qmin(p,k,ak*2+1,1+((pocz+kon)>>1),kon));
}
			
		
	

int main()
{
	ll n,m,nw,nww;
	int sum,me,l;
	ll wyn=1e18+9,ob,w;
	char z;
	scanf("%lld",&n);
	for(int i=1;i<=n;++i) scanf("%d",&twe[i]);
	scanf("%lld",&m);
	nw=nwd(n,m);
	nww=(ll)n*(ll)m/(ll)nw;
																		//printf("%lld %lld\n",nw,nww);
	for(int i=1;i<=m;++i)
	{
		scanf(" %c",&z);
		if(z=='W') twy[i]=1; else twy[i]=-1;
	}
	for(int i=1;i<=nw;++i)
	{
		sum=0;
		Init(m/nw*2+1);
		Insert(0,0);
		for(int j=i;j<=m;j+=nw) sum-=twy[j];
		if(sum<=0) continue;
		l=i;
		for(int j=1;j<=m/nw*2;++j) 
		{
			Insert(j,td[N+j-1].first+twy[1+((l-1)%m)]);			//UWAGA
			l=(l+n)%m;
			if(l==0) l=m;
		}
																		//for(int z=N;z<=N+m/nw*2;++z) printf("%d ",td[z].first); printf("\n");
		l=0;
																		//printf("%d\n",sum);
		for(int j=i;j<=n;j+=nw)
		{
			me=Qmin(l,l+m/nw)-td[N+l].first;
			ob=(twe[j]+me+sum-1)/sum;
			twe[j]-=ob*sum;
			w=n*((ll)Query(l,-1*twe[j]+td[N+l].first)-l-1)+j;
			wyn=min(wyn,ob*nww+w);
																		//Printf("%d %d %lld %d %d %lld\n",j,me,ob,twe[j],td[N+l].first,w);
			l=(l+(n%m)/nw)%(m/nw);
		}
	}
	if(wyn==1e18+9) printf("-1"); else printf("%lld",wyn);
	return 0;
}