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
#include <cstdio>
#include <algorithm>
#include <functional>

using std::printf;
using std::scanf;
using std::lower_bound;
using std::greater;
using std::min;

const int MAX = 1000000;

int n;
int friends[MAX];
int m;
char wins[MAX + 1];
int cyclePos[MAX];
int cycleStart[MAX];
int accumulatedMin[MAX];
int accumulatedSum[MAX];
int values[MAX];
bool visited[MAX] = { 0 };
int cycleLength;


int main()
{
  scanf("%d", &n);
  for (int i = 0; i < n; i++)
    scanf("%d", friends + i);

  scanf("%d", &m);
  scanf("%s", wins);

  int accumulatedMinI = 0;
  for (int wi = 0; wi < m; wi++)
  {
    if (visited[wi])
      continue;

    int sum = 0;
    int accumulatedMinVal = 10;
    int wpos = wi;
    cycleLength = 0;
    int cycleStartI = accumulatedMinI;
    do {
      cyclePos[wpos] = cycleLength;
      cycleStart[wpos] = cycleStartI;
      int val = wins[wpos] == 'W' ? 1 : -1;
      sum += val;
      accumulatedSum[accumulatedMinI] = sum;
      values[accumulatedMinI] = val;
      if (sum < accumulatedMinVal)
        accumulatedMinVal = sum;
      accumulatedMin[accumulatedMinI++] = accumulatedMinVal;

      cycleLength++;
      visited[wpos] = true;
      wpos = (wpos + n) % m;
    } while (wpos != wi);
  }

  long long failIndex = -1;
  for (int fi = 0; fi < n; fi++)
  {
    int cPos = cyclePos[fi % m];
    int cStart = cycleStart[fi % m];
    int * aSum = accumulatedSum + cStart;
    int cSum = aSum[cycleLength - 1];
    int * aMin = accumulatedMin + cStart;
    int * aValues = values + cStart;
    int fCash = friends[fi];

    int minDiffToEnd;
    if (cPos == 0)
      minDiffToEnd = aMin[cycleLength - 1];
    else
      minDiffToEnd = aMin[cycleLength - 1] - aMin[cPos] + aValues[cPos];

    int minDiffFromStart;
    if (cPos == 0)
      minDiffFromStart = 0;
    else
      minDiffFromStart = aMin[cPos - 1];

    int sumToEnd;
    if (cPos == 0)
      sumToEnd = aSum[cycleLength - 1];
    else
      sumToEnd = aSum[cycleLength - 1] - aSum[cPos - 1];

    int minDiff = min(minDiffToEnd, sumToEnd + minDiffFromStart);

    long long currentFailIndex = fi + 1;
    if (fCash + minDiff > 0)
    {
      if (cSum >= 0)
        continue;

      int cyclesMissed = (fCash + minDiff) / (-cSum);
      fCash += cSum * cyclesMissed;
      currentFailIndex += (long long)cyclesMissed * cycleLength * n;
    }

    if (fCash + minDiffToEnd <= 0)
    {
      int previuosCash = cPos == 0 ? 0 : aMin[cPos] - aSum[cPos];
      int * found = lower_bound(aMin + cPos, aMin + cycleLength, -fCash + previuosCash, greater<int>());
      int posDiff = found - (aMin + cPos);
      currentFailIndex += (long long)posDiff * n;
      if (failIndex == -1 || currentFailIndex < failIndex)
        failIndex = currentFailIndex;
      continue;
    }

    fCash += sumToEnd;
    currentFailIndex += (long long)(cycleLength - cPos) * n;

    int * found = lower_bound(aMin, aMin + cPos, -fCash, greater<int>());
    int posDiff = found - aMin;
    currentFailIndex += (long long)posDiff * n;
    if (failIndex == -1 || currentFailIndex < failIndex)
      failIndex = currentFailIndex;
  }

  printf("%lld\n", failIndex);
  return 0;
}