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
#include <bits/stdc++.h>
using namespace std;

int FirstGeq(const vector<int>& tree, int a, int lt, int rt, int l, int r, int value) {
  if (l > rt or r < lt)
    return -1;
  if (l <= lt and r >= rt) {
    if (tree[a] < value)
      return -1;
    int width = rt - lt + 1;
    while (width > 1) {
      if (tree[2 * a] >= value)
        a = 2 * a;
      else
        a = 2 * a + 1;
      width /= 2;
    }
    return a;
  }
  int mid = (lt + rt) / 2;
  int left = FirstGeq(tree, 2 * a, lt, mid, l, r, value);
  if (left != -1)
    return left;
  else
    return FirstGeq(tree, 2 * a + 1, mid + 1, rt, l, r, value);
}

int Max(const vector<int>& tree, int l, int r) {
  int T = tree.size() / 2;
  l += T; r += T;
  int res = max(tree[l], tree[r]);
  while (l/2 != r/2) {
    if (l % 2 == 0) res = max(res, tree[l + 1]);
    if (r % 2 == 1) res = max(res, tree[r - 1]);
    l /= 2;
    r /= 2;
  }
  return res;
}

int main() {
  int n;
  cin >> n;
  vector<int> budget(n);
  for (int i = 0; i < n; ++i)
    cin >> budget[i];
  int m;
  cin >> m;
  string machine;
  cin >> machine;
  assert(machine.length() == m);
  vector<vector<int>> cycles;
  vector<int> cycle_number(m, -1), pos_in_cycle(m);
  for (int i = 0; i < m; ++i) {
    if (cycle_number[i] != -1)
      continue;
    int new_cycle_number = cycles.size();
    cycles.push_back(vector<int>());
    vector<int>& cycle = cycles.back();
    int j = i, pos = 0;
    do {
      cycle_number[j] = new_cycle_number;
      pos_in_cycle[j] = pos;
      cycle.push_back(j);
      pos++;
      j = (j + n) % m;
    } while (j != i);
    assert(cycle.size() == cycles[0].size());
  }
  assert(cycles[0].size() * cycles.size() == m);
  int cycle_length = cycles[0].size();
  int T = 1;
  while (T < cycle_length + 1) T *= 2;
  vector<vector<int>> trees(cycles.size(), vector<int>(2 * T));
  for (int i = 0; i < cycles.size(); ++i) {
    for (int j = 0; j < cycle_length; ++j)
      trees[i][T + j + 1] = trees[i][T + j] + (machine[cycles[i][j]] == 'P' ? 1 : -1);
    for (int j = T - 1; j > 0; --j)
      trees[i][j] = max(trees[i][2 * j], trees[i][2 * j + 1]);
  }

  vector<long long> solutions;
  for (int i = 0; i < n; ++i) {
    int start_pos = i % m;
    int cycle_outcome = trees[cycle_number[start_pos]][T + cycle_length];
    const vector<int>& tree = trees[cycle_number[start_pos]];
    int pic = pos_in_cycle[start_pos];
    int max_loss = max(
        Max(tree, pic, cycle_length) - tree[T + pic],
        Max(tree, 0, pic) + tree[T + cycle_length] - tree[T + pic]);
    if (cycle_outcome <= 0 and max_loss < budget[i])
      continue;
    int full_cycles_before_bankrupcy = 
      budget[i] > max_loss ? (budget[i] - max_loss + cycle_outcome - 1) / cycle_outcome : 0;
    // cerr << "i = " << " budget = " << budget[i] << " max_loss = " << max_loss << " cycles_before_bankrupcy = " << full_cycles_before_bankrupcy << endl;
    int rest = budget[i] - cycle_outcome * full_cycles_before_bankrupcy;
    int which_turn = 0;
    int temp = FirstGeq(tree, 1, 0, T-1, pic, cycle_length, rest + tree[T + pic]);
    if (temp == -1) {
      which_turn = cycle_length - pic;
      temp = FirstGeq(tree, 1, 0, T-1, 0, pic, rest - (tree[T + cycle_length] - tree[T + pic]));
      assert(temp != -1);
      which_turn += temp - T;
    } else {
      which_turn = temp - T - pic;
    }
    // cerr << "which_turn = " << which_turn << endl;
    solutions.push_back(1 + i + (full_cycles_before_bankrupcy * (long long)cycle_length + which_turn - 1) * n);
    // cerr << i << " " << solutions.back() << endl;
  }

  if (solutions.empty())
    cout << -1 << endl;
  else
    cout << *min_element(solutions.begin(), solutions.end()) << endl;
}