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
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
#include <stdio.h>
#include <vector>
#include <string.h>

#define MAX_CYCLE 1000010
#define MAX_BOYS 1000010
#define MAX_VALUE 2000000000000000000


char cycleValues[MAX_CYCLE];
long long int visitedCycles[MAX_CYCLE];
int boys[MAX_BOYS];
int from_cycle_pos_to_cycle_val[MAX_BOYS];
long long int n;
long long int c;

typedef std::pair<int, int> IntPair;

long long int min(long long int a, long long int b){
	return a < b ? a : b;
}
long long int myAbs(long long int a){
	return a < 0 ? -a : a;
}

long long int countCycle(std::vector<int> & boysInCycle, std::vector<int> & cycle, std::vector<IntPair> & startPos){
	
	long long int sumaCyklu = 0;
	std::vector<int> cykleProgi;
	cykleProgi.push_back(-10000);//prosty ogranicznik by wartosci jakie trzeba uzyskac lezaly na swoich miejscach
	std::vector<IntPair> bestStarts(cycle.size(), IntPair(-1,-1));
	for (int i = 0; i < (int)cycle.size(); i++) from_cycle_pos_to_cycle_val[cycle[i]] = -1;
	for(int i = 0; i < (int)boysInCycle.size(); i++){
		int pos = startPos[boysInCycle[i]].first % cycle.size();//to odpowie nam na pytanie ktorzy jestesmy w cyklu, w sensie indeksu w cyklu
		//printf("================== %d\n", pos);
		if (bestStarts[pos].first == -1 || bestStarts[pos].first > boys[boysInCycle[i]]){//gdyz pierwszy element i tak zostatnie pierwszy zapisany
			bestStarts[pos].first = boys[boysInCycle[i]];
			bestStarts[pos].second = boysInCycle[i];
			from_cycle_pos_to_cycle_val[bestStarts[pos].second] = pos;
		}
	}

	//for(int i = 0; i < (int)bestStarts.size(); i++)	printf("start (%d) %d %d pozycja w wyseparowany cyklu %d\n", i, bestStarts[i].first, bestStarts[i].second, from_cycle_pos_to_cycle_val[bestStarts[i].second]);
	

	//iterujemy po cyklu zbierajac ludzi
	int lastBoyInCycle = bestStarts[0].second;
	//printf("------------%d\n", lastBoyInCycle);
	long long int  minValue = cycleValues[cycle[0]] == 'W' ? boys[lastBoyInCycle] + 1 : boys[lastBoyInCycle] - 1;
	sumaCyklu = cycleValues[cycle[0]] == 'W' ? sumaCyklu + 1 : sumaCyklu - 1;
	if (-sumaCyklu >= (int)cykleProgi.size()) cykleProgi.push_back(0);
	int cycleStart = 0;

	//printf("nastepny (%d) %d %d\n", cycle[0], lastBoyInCycle, minValue);
	//printf("CYKL DLUGOSCI %d\n", cycle.size());
	long long int wykonaneKroki = n;
	for (int i = 1; i < (int)cycle.size(); i++){
		int nextBoyInCycle = from_cycle_pos_to_cycle_val[cycle[i]] > -1 ? bestStarts[from_cycle_pos_to_cycle_val[cycle[i]]].second : -1;
		//printf("pobieramy informacje o kolejnym elemencie %d %d %d\n", nextBoyInCycle, cycle[i], from_cycle_pos_to_cycle_val[cycle[i]]);
		if (nextBoyInCycle > -1){
			long long int  nowyKoszt = boys[nextBoyInCycle];
			//printf("poprzdni (%d %lld  kr %lld) nastepny (%d) %d %lld\n", lastBoyInCycle, minValue, wykonaneKroki, cycle[i], nextBoyInCycle, nowyKoszt);
			//if (minValue > nowyKoszt || (minValue == nowyKoszt && lastBoyInCycle < nextBoyInCycle)){
			if (minValue > nowyKoszt || (minValue == nowyKoszt && wykonaneKroki >= nextBoyInCycle)){
				minValue = nowyKoszt;
				lastBoyInCycle = nextBoyInCycle;
				cycleStart = i;
				wykonaneKroki = nextBoyInCycle + n;//kazdego na cyklu zgarniemy tylko raz i wejdziemy znow po n krokach
			}	else {
				wykonaneKroki += n;//wraz z kazdym nowym krokiem
			}
		}
		else {
			//printf("NIE MAMY SIE Z KIM POROWNAC\n");
			wykonaneKroki += n;//wraz z kazdym nowym krokiem
		}
		//minimalny nowy koszt bierzemy za aktualny i dopiero go zenijszamy
		minValue = cycleValues[cycle[i]] == 'W' ? minValue + 1 : minValue - 1;
		sumaCyklu = cycleValues[cycle[i]] == 'W' ? sumaCyklu + 1 : sumaCyklu - 1;
		if (-sumaCyklu >= (int)cykleProgi.size()) cykleProgi.push_back(i);

		//printf("nowy koszt %lld dla chlopca %d wykonal krokow %lld\n", minValue, lastBoyInCycle, wykonaneKroki);
		if (minValue == 0) {
			//printf("not finished cycle\n");
			break;
		}
	}

	//liczymy liczbe krokow
	long long int kroki = 0;
	long long int suma = boys[lastBoyInCycle];
	for(int i = 0; i < (int) cycle.size(); i++){//jesli element od ktorego wystartujemy bediz epierwszy to nie wykonany zadnego obrotu petli tylko przeliczymy wynik
		if (cycleStart == 0) break;
		//printf("kroki (%d) cyklu %d\n", lastBoyInCycle, cycle[cycleStart]);
		suma = cycleValues[cycle[cycleStart]] == 'W' ? suma + 1 : suma - 1;
		if (suma == 0) break;

		cycleStart = (cycleStart + 1) % cycle.size();
		kroki++;
	}
	long long int krokiWykonaneDoPozycji = kroki * n + lastBoyInCycle + 1;//gdyz tutaj pozycja zakonczyla sie zerem zatem nie startujemy lecz wlasnie skonczylismy
	//printf("last boy %d  total moves %lld zostala suma %lld suma cyklu %lld\n", lastBoyInCycle, krokiWykonaneDoPozycji, suma, sumaCyklu);//+1 gdyz interesuje nas stan po ruszeniu sie

	//for(int i = 0; i < (int)cykleProgi.size(); i++) 	printf("progi %d\n", cykleProgi[i]);
	
	
	if (suma == 0){
		return krokiWykonaneDoPozycji;
	} else if (suma > 0 && sumaCyklu >= 0) {//minimalna suma po przejscu cyklu powyzej zera i caly cykl neiujemny wiec krecimy sie w neiskonczonsc
		return MAX_VALUE;
	} else {//suma dodatnia ale cykl ma ujemna wartosc, zatem trzeab przeliczyc ile razy go obrocimy
		long long int result = 0;
		//printf("SUMA %lld %ld %lld\n", suma, cykleProgi.size(), sumaCyklu);
		long long int liczbaIteracji = (suma - (long long int)cykleProgi.size() + 1) / myAbs(sumaCyklu);
		suma += sumaCyklu * liczbaIteracji;
		result += n * liczbaIteracji * (long long int)cycle.size();
		if (suma >= (long long int)cykleProgi.size()){
			result += n * (long long int)cycle.size();
			suma += sumaCyklu;
		}
		/*
		while(suma >= (long long int)cykleProgi.size()){
			result += n * (long long int)cycle.size();//kazdy jeden przeskok w cyklu to jeden obrot, a tu musimy wykonac caly cykl
			suma += sumaCyklu;
		}*/

		//printf("===========%lld %d %lld %lld\n", suma, (int)cykleProgi.size(), liczbaIteracji, sumaCyklu);
		if (suma > 0)
			result += n * cykleProgi[suma] + krokiWykonaneDoPozycji;//potem jeszcze tylko tyle skokow ile potrzeba do wyzerowania sumy
		else 
			result += krokiWykonaneDoPozycji;
		return result;
	}

}


int main(){

	scanf("%lld", &n);
	std::vector<IntPair> startPos(n, IntPair(0,0));
	memset(visitedCycles,0, MAX_CYCLE);
	for (int i = 0; i < n; i++) scanf("%d", &boys[i]);
	scanf("%lld %s", &c, cycleValues);
	std::vector<std::vector<int> > cycles;

	std::vector<std::vector<int> > boysInCycles;
	int pos = 0;

	//printf("wczytal\n");
	for (int i = 0; i < n; i++){
		pos = i % c;
		//printf("punkt startowy %d\n",pos);
		
		
		if (visitedCycles[pos] == 0) {
			cycles.push_back(std::vector<int>());
			boysInCycles.push_back(std::vector<int>());
		}



		while (visitedCycles[pos] == 0){
			cycles.back().push_back(pos);
			visitedCycles[pos] = cycles.size();
			pos = (pos + n) % c;
		}
		startPos[i].second = visitedCycles[pos] - 1;//numer cyklu
		boysInCycles[startPos[i].second].push_back(i);
		startPos[i].first = boysInCycles[startPos[i].second].size() - 1 ;//to odpowiada na pytanie ktorzy tak na prawde ejstesmy w cyklu
		
	}
	std::vector<std::vector<int> > cyclesValues;
	/*
	for (int i = 0; i < (int)cycles.size(); i++){
		for (int j = 0; j < (int)cycles[i].size(); j++)
			printf("%d ", cycles[i][j]);
		printf("CYKL\n");
	}*/
	/*
	printf("CHLOPCY W CYKLACH \n");
	for (int i = 0; i < (int)boysInCycles.size(); i++){
		for (int j = 0; j < (int)boysInCycles[i].size(); j++)
			//printf("(%d %d) ", boysInCycles[i][j].first, boysInCycles[i][j].second);
			printf("(%d %d) ", boysInCycles[i][j], boys[boysInCycles[i][j]]);
		printf("\n");
	}*/
	//for (int i = 0; i < n; i++)		printf("%d startuje w cyklu %d w pozycji %d\n", i, startPos[i].second, startPos[i].first);
	//printf("przeliczyl\n");

	long long int minCycleVal = MAX_VALUE;
	for(int i = 0; i < (int)boysInCycles.size(); i++){
		long long int t = countCycle(boysInCycles[i], cycles[i], startPos);
		//printf("wynik cyklu %d %lld\n",i, t);
		minCycleVal = min(minCycleVal,t);
	}
	if (minCycleVal == MAX_VALUE){
		printf("-1\n");
	}	else {
		printf("%lld\n", minCycleVal);
	}

	return 0;
}