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
#include <algorithm>
#include <cassert>
#include <cstdio>
#include <deque>
#include <vector>
using namespace std;

constexpr int MAXN = 1000010;
constexpr int MAXM = 1000010;
int N;
int M;
int money[MAXN];
int win_or_loss[MAXM];

// how many rounds x can play (-1 -> inf)
long long lasts_rounds[MAXN];

void read_data() {
  scanf("%d", &N);
  for (int i = 0; i < N; ++i) {
    scanf("%d", money + i);
    lasts_rounds[i] = -2; // dunno
  }
  scanf("%d\n", &M);
  std::vector<char> str(M + 1, 'X');
  fgets(str.data(), M, stdin);
  for (int i = 0; i < M; ++i) {
    win_or_loss[i] = str[i] == 'W' ? 1 : -1;
  }

  //  printf("%d\n", N);
  //  for (int i = 0; i < N; ++i) {
  //    printf("%d: %d\n", i, money[i]);
  //  }
  //  printf("%d\n", M);
  //  for (int i = 0; i < M; ++i) {
  //    printf("%d: %d\n", i, win_or_loss[i]);
  //  }
}

void rot(deque<pair<int, int>>& mins, deque<int>& cycle_indexes, int& vertical_offset, int& horizontal_offset) {
//     assert(!mins.empty());
    int back = cycle_indexes.back();
    cycle_indexes.pop_back();
    cycle_indexes.push_front(back);
    ++horizontal_offset;

    if (win_or_loss[cycle_indexes.front()] == 1) {
//       printf("moving up slope\n");
      ++vertical_offset;
      // remove above zeros from the beginning
      while (!mins.empty() && mins.front().first + vertical_offset >= 0) {
        mins.pop_front();
      }
      // put (0, 0) if the first is up
      mins.emplace_front(-vertical_offset, -horizontal_offset);
    } else {
//       printf("moving down slope\n");
      --vertical_offset;
//       printf("second %d hori_off %d size %d\n", mins.back().second, horizontal_offset, cycle_indexes.size());
      if (mins.back().second + horizontal_offset - 1 == cycle_indexes.size()) {
        // the last down slope becomes shorter
        ++mins.back().first;
        --mins.back().second;
        if (mins.size() >= 2 && mins[mins.size() - 2].first <= mins.back().first) {
          mins.pop_back();
        }
      }
    }
}

int ceill(int a, int b) {
  return (a + b - 1) / b;
}

void compute_lasts(int idx, int net_diff, const deque<pair<int, int>>& mins,
                   const deque<int>& cycle_indexes, int vertical_offset, int horizontal_offset) {
//   printf("comp_lasts %d %d\n", idx, net_diff);
//     for (int it = 0; it < cycle_indexes.size(); ++it) {
//       printf("ci %d: %d\n", it, cycle_indexes[it]);
//     }
//     for (int it = 0; it < mins.size(); ++it) {
//       printf("mins %d: %d %d\n", it, mins[it].first + vertical_offset, mins[it].second + horizontal_offset);
//     }
//   assert(!mins.empty());

  for (int i = idx; i < N; i += M) {
    int min_of_mins = mins.back().first + vertical_offset;
//     printf(" lasts %d == ? (mon %d min %d)\n", i, money[i], min_of_mins);
    if (money[i] > -min_of_mins && net_diff >= 0) {
      // he'll last foreva
      lasts_rounds[i] = -1;
//       printf("foreva\n");
      continue;
    }
    lasts_rounds[i] = 0;
    if (net_diff < 0) {
      // it'll take him r cycles until he has less than or eq -min_of_mins
      int r = ceill(money[i] + min_of_mins, -net_diff);
      r = max(0, r);
      lasts_rounds[i] = (long long) r * (long long) cycle_indexes.size();
      money[i] += r * net_diff; // += (<0)
    }
//     printf("lasts %lld money %d\n", lasts_rounds[i], money[i]);
    // find first min which is less (whose abs is less) than current money[i]
    auto it = lower_bound(mins.begin(), mins.end(), money[i], [vertical_offset](const pair<int, int>& p, int v) {
      return -(p.first + vertical_offset) < v;
    });
//     printf(" low_bnd %d %d\n", it->first + vertical_offset, it->second + horizontal_offset);
    lasts_rounds[i] += it->second + horizontal_offset - (-(it->first + vertical_offset) - money[i]);
  }
}

void compute_defeat_times(int curr) {
//   printf("cdt %d\n", curr);
//   assert(curr < M);
  deque<int> cycle_indexes;

  int last = -1;
  int init_curr = curr;
  do {
    cycle_indexes.push_back(curr);
    curr = (curr + N) % M;
  } while (curr != init_curr);

  // fill initial mins (for initial curr)
  int vertical_offset = 0;
  int horizontal_offset = 0;
  // value, position
  deque<pair<int, int>> mins;

  int curr_value = 0;
  mins.emplace_back(0, 0);
  //  curr = init_curr;
  for (int i = 0; i < cycle_indexes.size(); ++i) {
    curr_value += win_or_loss[cycle_indexes[i]];
//     printf("cv %d %d\n", curr_value, cycle_indexes[i]);
    if (curr_value == mins.back().first - 1 && i == mins.back().second) {
      ++mins.back().second;
      --mins.back().first;
    } else if (curr_value < mins.back().first) {
      mins.emplace_back(curr_value, i + 1);
    }
  }

   compute_lasts(cycle_indexes.front(), curr_value,mins, cycle_indexes, vertical_offset, horizontal_offset);

   for (int i = 1; i < cycle_indexes.size(); ++i) {
     // rotate graph
     rot(mins, cycle_indexes, vertical_offset, horizontal_offset);

    compute_lasts(cycle_indexes.front(), curr_value,mins, cycle_indexes, vertical_offset, horizontal_offset);
   }
}

void compute_defeat_times() {
  for (int i = 0; i < N; ++i) {
    if (lasts_rounds[i] == -2) {
      // not computed
      compute_defeat_times(i);
    }
  }

//   for (int i = 0; i < N; ++i) {
//     printf("lasts %d -> %lld\n", i, lasts_rounds[i]);
//   }
}

long long compute_result() {
  long long min = -2;
  long long pos = -2;
  for (int i = 0; i < N; ++i) {
    if (lasts_rounds[i] != -1 && (min == -2 || lasts_rounds[i] < min)) {
      min = lasts_rounds[i];
      pos = i;
    }
  }
  if (min == -2) {
    return -1;
  }
//   printf("%lld %d\n", min, pos);
  return (min - 1) * N + pos + 1;
}

int main() {
  read_data();
  compute_defeat_times();
  printf("%lld\n", compute_result());
}