Description：

$n$ 个人轮流玩赌博机，编号为 $i$ 的人有 $a[i]$ 元钱。赌博机是一个长度为 $m$ 的 $1$ 和 $-1$ 的环，每个人循环操作，问第一次是什么时候有人没钱了。

$1\leqslant n\leqslant 10^6$

Solution：

首先需要求出来一个 $mn[i]$ 表示从赌博机的第 $i$ 个位置开始的在一次循环中最小能到达的位置，这个可以把每个环找出来倍长，然后从后往前依次计算答案，如果从某个位置开始更小，就更新，否则沿用上一个的加上这一位的值，然后我们想要知道他死在了第几个环上，那么就要求满足： $$ a[i]+t\times S[k]+mn[k]\leqslant 0,a[i]+(t-1)\times S[k]+mn[k]>0\\ \Rightarrow\lceil\frac{a[i]+mn[k]}{-S[k]}\rceil=t $$ 也就是说他会死在第 $t+1$ 个环上，那么我们就分别判断这个位置是否合法，也就是说我们现在有很多询问，每个询问形如查询在从第 $p[i]$ 个位置开始的环上初始为 $a[i]$ 会死在哪里，这个可以把所有询问离线，然后对于每个环还是倍长，从后往前扫，同时维护一个桶记录每个值在扫描线之后第一次出现的位置，然后在扫描到区间左端点的时候就可以计算答案了。

Code：

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<map>

#include<vector>

#include<cctype>

#include<cstring>

using namespace std;

int n;

#define MAXN 1000010

int a[MAXN];

int m;

int v[MAXN],s[MAXN],mn[MAXN];

int getc()

{

	register char c = getchar();

	while(!isalpha(c))c = getchar();

	return (c == 'W' ? 1 : -1);

}

int gcd(int a,int b){return (b == 0 ? a : gcd(b,a % b));}

long long t[MAXN];

int circ[MAXN << 1],pre[MAXN << 1];

int pq[MAXN << 1],head,tail;

int minv[MAXN];

int l,g;

struct query

{

	int p,a,ans;

}q[MAXN];

vector<int> v1[MAXN];

vector<int> v2[MAXN];

map<int,int> bas;

void work()

{

	/*for(int i = 0;i < n;++i)

	{

		if(q[i].a == 0)continue;//cout << "!!! " << q[i].p << " " << q[i].a << endl;

		for(int k = q[i].p,j = 1;j <= l;++j,k = (k + n) % m)

		{

			q[i].a += v[k];

			if(q[i].a == 0)

			{//cout << "###" << endl;

				q[i].ans = j;

				break;

			}

		}

	}*/

	for(int i = 0;i < n;++i)

	{

		if(q[i].a == 0)continue;

		v1[q[i].p % g].push_back(i);

	}

	for(int i = 0;i < g;++i)

	{

		for(vector<int>::iterator it = v1[i].begin();it != v1[i].end();++it)

		{

			v2[q[*it].p].push_back(*it);

		}

		for(int k = i,j = 1;j <= l;++j,k = (k + n) % m)

		{

			circ[j] = k;

			pre[j] = pre[j - 1] + v[circ[j]];

		}

		for(int j = l + 1;j <= 2 * l;++j)circ[j] = circ[j - l],pre[j] = pre[j - 1] + v[circ[j]];

		bas.clear();

		for(int j = 2 * l;j >= 1;--j)

		{

			bas[pre[j]] = j;

			for(vector<int>::iterator it = v2[circ[j]].begin();it != v2[circ[j]].end();++it)

			{//cout << " -> " << *it << endl;

				q[*it].ans = bas[-q[*it].a + pre[j - 1]] - j + 1;

			}

		}

	}

	return;

}

int main()

{

	freopen("c.in","r",stdin);

	freopen("c.out","w",stdout);

	scanf("%d",&n);

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

	scanf("%d",&m);

	for(int i = 0;i < m;++i)v[i] = getc();

	l = m / gcd(n,m);

	g = gcd(n,m); 

	for(int i = 0;i < g;++i)

	{

		circ[0] = 0;

		for(int k = i,j = 1;j <= l;++j,k = (k + n) % m)circ[j] = v[k];

		for(int j = 1;j <= l;++j)circ[j + l] = circ[j];

		int sum = 0;

		for(int k = i,j = 1;j <= l;++j,k = (k + n) % m)sum += v[k];

		for(int k = i,j = 1;j <= l;++j,k = (k + n) % m)s[k] = sum;

		for(int j = 1;j <= 2 * l;++j)pre[j] = pre[j - 1] + circ[j];

		head = 1;tail = 0;

		for(int p = 1;p < l;++p)

		{

			while(head <= tail && pre[pq[tail]] >= pre[p])--tail;

			pq[++tail] = p;

		}

		for(int p = l;p < 2 * l;++p)

		{

			while(head <= tail && pre[pq[tail]] >= pre[p])--tail;

			pq[++tail] = p;

			while(head <= tail && p - pq[head] + 1 > l)++head;

			minv[p - l + 1] = pre[pq[head]] - pre[p - l];

		}

		for(int k = i,j = 1;j <= l;++j,k = (k + n) % m)mn[k] = minv[j];

	}

	long long ans = 0x3f3f3f3f3f3f3f3f;

	for(int i = 0;i < n;++i)

	{

		t[i] = 0;

		if(s[i % m] >= 0)

		{

			if(a[i] + mn[i % m] > 0)

			{

				t[i] = -1;

				continue;

			}

			q[i].p = i % m;q[i].a = a[i];

		}

		else

		{

			if(a[i] <= -mn[i % m])

			{

				q[i].p = i % m;q[i].a = a[i];

			}

			else

			{

				int ti = (int)ceil(1.0 * (a[i] + mn[i % m]) / (-s[i % m]));//cout << i << " " << ti << endl;

				t[i] = 1ll * ti * l;

				q[i].p = i % m;q[i].a = a[i] + 1ll * ti * s[i % m];

			}

		}

	}

	work();

	for(int i = 0;i < n;++i)

	{

		if(t[i] == -1)continue;

		t[i] += q[i].ans;//cout << t[i] << " ";

		ans = min(ans,i + 1 + 1ll * (t[i] - 1) * n);

	}//cout << endl;

	if(ans != 0x3f3f3f3f3f3f3f3f)cout << ans << endl;

	else puts("-1");

	fclose(stdin);

	fclose(stdout);

	return 0;

}