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
#include<iostream>
#include<vector>

using namespace std;

const int maxn = 1000002;

int n, chlop[ maxn ], m, j;
long long cur_one, cur_res;
char autom[ maxn * 2 ], t_char;
bool used[ maxn ], found;
vector< int > maybe;

long long loop( int start ) {
//cout << "testuje gostka " << start << endl;	
	long long cur = chlop[ start ], local_delta = 0, local_delta_step = 0, global_delta = 0, step = 0; 
	long long k = start, odl_k;
	if( k > m ) k = ( ( k - 1 ) % m ) + 1;
	do {
		step++;
		global_delta += autom[ k ];
		if( cur + global_delta < 1 ) {
			return ( long long )start + ( ( step - 1 ) * n );
		}
		if( global_delta < local_delta ) {
			local_delta = global_delta;
			local_delta_step = step;
		}
		k += n;
		if( k > m ) k = ( ( k - 1 ) % m ) + 1;
	} while( k != start );
//cout << "dostalem gd = " << global_delta << endl << "dostalem ld = " << local_delta << endl;
	long long tres = start - 1;
	if( local_delta >= 0 ) return -1;
	else if( global_delta >= 0 ) {
		return -1;
	}
	long long t_int = ( cur + local_delta ) / global_delta;
	t_int = -t_int;
//	if( ( ( cur + local_delta ) + t_int * global_delta ) > 0 ) t_int++;
	tres += t_int * step * n;
//cout << "na pelne przebiegi potrzeba nam " << tres << " czasu" << endl;
	if( ( cur + t_int * global_delta ) == 0 ) return tres;
	cur = cur + t_int * global_delta;
	k = start; 
	while( true ) { 
		tres += n;
		cur += autom[ k ];
		if( cur < 1 ) return ( tres - n + 1 );
		k += n;
		if( k > m ) k = ( ( k - 1 ) % m ) + 1;
	}

}

int main() {
	ios_base::sync_with_stdio( 0 );
	cin >> n;
	for( int i = 1; i <= n; i++ ) cin >> chlop[ i ];
	cin >> m;
	for( int i = 1; i <= m; i++ ) {
		cin >> t_char;
		autom[ i ] = ( ( t_char == 'W' ) ? 1 : -1 );
	}

	int orig_m = m;
	if( n > m ) {
		if( ( n % m ) == 0 ) m *= ( n / m );
		else m *= ( ( n / m ) + 1 );
	}

	for( int i = orig_m + 1; i <= m; i++ ) autom[ i ] = autom[ i - orig_m ];

	for( int i = 1; i <= n; i++ ) {
		if( !used[ i ] ) {
//cout << "testuje cykl chlopka " << i << endl;
			found = false;
			cur_res = chlop[ i ];
			cur_one = i;
			j = i;
			if( j > m ) j = ( ( j - 1 ) % m ) + 1;
			do {
//cout << "rozwazam j = " << j << endl;
				if( j <= n ) used[ j ] = true;
				if( found == false ) {
					if( j <= n ) {
						if( chlop[ j ] <= cur_res ) {
							cur_res = chlop[ j ];
							cur_one = j;
						}
					}
					cur_res += autom[ j ];
					if( cur_res < 1 ) {
						found = true;
						maybe.push_back( cur_one ); 
//cout << "znalazlem przed czasem gostka " << cur_one << endl;
					}
				}
				j += n;
				if( j > m ) j = ( ( j - 1 ) % m ) + 1; 
			} while( j != i );
			if( found == false ) maybe.push_back( cur_one );		
//cout << "znalazlem gostka " << cur_one << endl;
		}
	}
	cur_res = -1;
	for( vector< int >::iterator it = maybe.begin(); it != maybe.end(); it++ ) {
		cur_one = loop( *it );
		if( cur_one > -1 ) {
			if( cur_res == -1 ) {
				cur_res = cur_one;
			}
			else if( cur_one < cur_res ) {
				cur_res = cur_one;
			}
		}
	}
	cout << cur_res << endl;
}