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

const long long int NN = 1000 * 1000 + 7, MAXX = 9223372036854775807LL;

long long int tab[NN], gra[NN], kol[NN], ch[NN], w[NN], m, n, d, a, c, s, wyn;
char cc;

long long int nwd(long long int i,long long int j)
{
  long long int k;
  while (i > 0)
  {
     k = i;
	 i = j % i; 
	 j = k;
  }
  return j;
}

long long int i, j;

int main()
{
ios_base::sync_with_stdio(0);

cin >> n;
for(i = 0; i < n; i++)
{
	cin >> ch[i];
	gra[i] = -1;
}
cin >> m;
for (i = 0; i < m; i++)
{
	cin >> cc;
	if (cc=='W') w[i] = 1;
	else w[i] = -1;
}

d = nwd(m, n);
//cout << "MAXX: " << MAXX << "\n";
//cout << "d: " << d << "\n";
wyn = MAXX;
//cout << "wyn: " << wyn << "\n";

for (c = 0; c < d; c++)
{
	j = c;
	s = 0;
	a = -1;
	for (i = 0; i < m / d; i++)
	{
		kol[m / d - 1 - i] = j;
		j = (j + n) % m;
	}
/*	
	for (j = 0; j < m / d; j++)
			cout << kol[j] << " ";
		cout << "\n";
*/	
	for (i = 0; i < m / d; i++)
	{
		s = s + w[kol[i]];
//		cout << "s: " << s << "\n";
		if (w[kol[i]] < 0)
		{
			a++;
			tab[a] = i;
		}
		else
			if (a >= 0) a--;
/*		for (j = 0; j <= a ; j++)
			cout << tab[j] << " ";
		cout << "\n";
*/		for (j = kol[i]; j < n; j = j + m)
		{
			if (ch[j] > a + 1)
			{
				ch[j] = ch[j] + s;
				gra[j] = i;
			}
			else
			{
				gra[j] = i - tab[a - ch[j] + 1];
				ch[j] = 0;
			}
//			cout << "j: " << j << " " << ch[j] << " " << gra[j] << "\n";
		}
	}
	
	for (i = c; i < n; i = i + d)
	{
		if ((ch[i] > a + 1) && (s >= 0))
		{
			gra[i] = -1;
			ch[i] = 0;
		}
		if (ch[i] > 0)
		{
			if (ch[i] > a + 1)
			{
				j = ((ch[i] - a - 2) / ((-1)*s)) + 1;
				gra[i] = gra[i] + (m / d) * j;
				ch[i] = ch[i] + s * j;
			}
			gra[i] = gra[i] + (m / d) - tab[a + 1 - ch[i]];
		}
		if (gra[i] != (-1))
			wyn = min(wyn, gra[i] * n + i + 1);
/*		cout << "i: " << i << " " << gra[i] << " " << gra[i] * n + i + 1 << "\n";
		cout << "wyn: " << wyn << "\n";*/
	}
}

if (wyn==MAXX) cout << -1;
else cout << wyn;

return 0;
}