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
#include<algorithm>
#include<cstdio>
#include<list>
#include<queue>
#include<utility>
#include<vector>

#define BOYS 1000000
#define CYCLE 1000000

#define FOR(i, a, b) for (int i = (a); i < (b); ++i)
#define REP(i, n) FOR(i, 0, n)
using namespace std;

struct container {  // random access container with front and back operation
  vector<int> elements;
  int start = 0;
  
  void push_front(int a) {
    if (start == 0) {
      vector<int> new_elements(elements.size() + 1, 0);
      start = elements.size() + 1;
      for (int element : elements) {
        new_elements.push_back(element);
      }
      elements.swap(new_elements);
    }
    elements[--start] = a;
  }

  void push_back(int a) {
    elements.push_back(a);
  }
  void pop_front() {
    //if (size() == 0) {
    //  throw 1;
    //}
    start++;
  }
  
  void pop_back() {
    elements.pop_back();
  }

  int size() {
    return elements.size() - start;
  }
  
  bool empty() {
    return size() == 0;
  }
  
  int operator [](int a) {
    return elements[start + a];
  }
};

struct data {
  int sum, cnt;
  container descending_indexes;
  data(int sum, int cnt, container descending_indexes) :
      sum(sum),
      cnt(cnt),
      descending_indexes(descending_indexes) {}
};

int savings[BOYS];
char cycle[CYCLE + 1];
bool processed[CYCLE];
vector<data> quick_info;
long long moves[BOYS];

int main() {
  int n, m;
  scanf("%d", &n);
  REP(i, n) {
    scanf("%d", savings + i);
  }
  scanf("%d%s", &m, cycle);
  REP(i, m) {
    processed[i] = false;
  }
  REP(i, m) {
    if (!processed[i]) {
      int ii = i, cnt = 0, sum = 0;
      container descending_indexes;
      do {
        int delta = (cycle[ii] == 'W' ? 1 : -1);
        sum += delta;
        if ((descending_indexes.empty() && (sum < 0)) ||
            (!descending_indexes.empty() &&
                (sum < -descending_indexes.size()))) {
          descending_indexes.push_back(cnt);
        }
        processed[ii] = true;
        ii = (ii + n) % m, ++cnt;
      } while(ii != i);
      quick_info.push_back(data(sum, cnt, descending_indexes));
    }
  }
  REP(i, quick_info.size()) {
    int ii = i, relative_position = 0;
    do {
      int iii = ii;
      while (iii < n) {
        if ((quick_info[i].sum < 0) || (quick_info[i].descending_indexes.size() >= savings[iii])) {
          if (savings[iii] <= quick_info[i].descending_indexes.size()) {
            moves[iii] = quick_info[i].descending_indexes[savings[iii] - 1] -
                relative_position;
          } else {
            long long x =
                (savings[iii] - quick_info[i].descending_indexes.size() - quick_info[i].sum - 1)
                    / (- quick_info[i].sum);
            moves[iii] = x * quick_info[i].cnt +
                quick_info[i].descending_indexes[(savings[iii] - x * (- quick_info[i].sum)) - 1] -
                relative_position;
          }
        } else {
          moves[iii] = -1;
        }
        iii += m;
      }
      ii = ((ii - n) % m + m) % m, relative_position--;
      if (cycle[ii] == 'W') {
        if (!quick_info[i].descending_indexes.empty()) {
          quick_info[i].descending_indexes.pop_front();
        }
      } else {
        quick_info[i].descending_indexes.push_front(relative_position);
        if (quick_info[i].descending_indexes[quick_info[i].descending_indexes.size() - 1] == (relative_position + quick_info[i].cnt)) {
          quick_info[i].descending_indexes.pop_back();
        }
      }
    } while (ii != i);
  }
  long long expected_finish = -1;
  REP(i, n) {
    if (moves[i] != -1) {
      long long expected_time = n * moves[i] + i + 1;
      if ((expected_finish == -1) || (expected_finish > expected_time)) {
        expected_finish = expected_time;
      }
    }
  }
  printf("%lld\n", expected_finish);
  return 0;
}