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


void preproces_rmq(std::vector<std::vector<int>> &_rmq, int _log, std::vector<int> const &_cumsum)
{
	for (int i = 0; i < _rmq.size(); ++i) {
		_rmq[i].resize(_log);
		_rmq[i][0] = i;
	}
	int n = _cumsum.size();
	for (long long j = 1; (1 << j) <= n; ++j) {
		for (long long i = 0; i + (1 << j) - 1 < n; ++i) {
			if (_cumsum[_rmq[i][j - 1]] < _cumsum[_rmq[i + (1 << (j - 1))][j - 1]]) {
				_rmq[i][j] = _rmq[i][j - 1];
			} else {
				_rmq[i][j] = _rmq[i + (1 << (j - 1))][j - 1];
			}
		}
	}
}

inline long long min_query(std::vector<std::vector<int>> const &_rmq, std::vector<int> const &_cumsum, int _a, int _b)
{
	int k = std::log2(_b - _a + 1);
	int va = _cumsum[_rmq[_a][k]];
	int vb = _cumsum[_rmq[_b - (1 << k) + 1][k]];
	return va <= vb ? va : vb;
}


void subseq(std::vector<int> const &_players, std::vector<int> const &_values, int _start, int _len, int _paths, std::vector<long long> &_out)
{
	int min_len = _len * 2 + 1;
	int log_len = std::log2(min_len) + 1;

	std::vector<int> cumsum(min_len, 0);
	std::vector<std::vector<int>> minimums(1 << log_len);
	int lowest = 0, highest = 0;

	cumsum[0] = 0;
	int rep = 1;
	int hop = _players.size();
	int length = _values.size();
	int idx = 1;
	int pos = _start;
	do {
		cumsum[idx] = cumsum[idx - 1] + _values[pos];
		highest = std::max(highest, cumsum[idx]);
		pos = (pos + hop) % length;
		++idx;
	} while (pos != _start || rep--);

	preproces_rmq(minimums, log_len + 1, cumsum);
	lowest = min_query(minimums, cumsum, 1, _len * 2);
	std::vector<int> is(highest - lowest + 1, 0);
	std::vector<std::vector<int>> positions(highest - lowest + 1);
	for (int i = 1; i < _len * 2 + 1; ++i) {
		positions[cumsum[i] - lowest].push_back(i);
	}

	int players_count = hop / _paths;
	int pidx = 0;
	std::vector<std::vector<long long>> players(_len);
	do {
		int offset = pos + (pidx / length) * length;
		players[(offset % length) / _paths].push_back(pidx);
		pos = (pos + hop) % length;
		++pidx;
	} while (pidx < players_count);

	idx = 1;
	for (auto &s : players) {
		for (auto &p : s) {
			int player = p * _paths + _start;
			int minimum = min_query(minimums, cumsum, idx, idx + _len) - cumsum[idx - 1];
			if (_players[player] + minimum > 0) {
				if (cumsum[_len] >= 0) {
					_out[player] = -1;
				} else {
					long long games = (_players[player] + minimum) / (-cumsum[_len]);
					if (_players[player] + minimum + games * cumsum[_len] > 0) {
						++games;
					}
					int minpos = -(_players[player] + games * cumsum[_len]) + cumsum[idx - 1] - lowest;
					while (positions[minpos][is[minpos]] < idx) {
						++is[minpos];
					}
					_out[player] = games * _len + positions[minpos][is[minpos]] - idx + 1;
				}
			} else {
				int minpos = (-_players[player]) + cumsum[idx - 1] - lowest;
				while (positions[minpos][is[minpos]] < idx) {
					++is[minpos];
				}
				_out[player] = positions[minpos][is[minpos]] - idx + 1;
			}
		}
		++idx;
	}
}

int gcd(int _a, int _b)
{
	int c;
	while (_b != 0) {
		c = _a % _b;
		_a = _b;
		_b = c;
	}
	return _a;
}

int main()
{
	std::ios::sync_with_stdio(false);

	int n, m;

	std::cin >> n;
	std::vector<int> k(n);
	for (int i = 0; i < n; ++i) {
		std::cin >> k[i];
	}

	std::cin >> m;
	std::vector<int> l(m);
	for (int i = 0; i < m; ++i) {
		char tmp; std::cin >> tmp;
		l[i] = tmp == 'P' ? -1 : 1;
	}

	int paths = gcd(n, m);
	std::vector<long long> players(n);
	for (int i = 0; i < paths; ++i) {
		subseq(k, l, i, m / paths, paths, players);
	}

	long long least = std::numeric_limits<long long>::max(), idx;
	for (int i = 0; i < n; ++i) {
		if (players[i] > 0 && least > players[i]) {
			least = players[i];
			idx = i;
		}
	}

	std::cout << (least == std::numeric_limits<long long>::max() ? -1 : least * (idx + 1) + (least - 1) * (n - idx - 1)) << std::endl;
	return 0;
}