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

using namespace std;
const int N = 1000005, C = 2000000;

int n, m;
long long money[N];
char state[N];
bool vis[N];
vector<long long> start[N];

struct Queue {
    vector<int>v;
    int poc = 0;
    void push(int w) {
        v.push_back(w);
    }
    void pop() {
        poc++;
    }
    int front() {
        return v[poc];
    }
    bool empty() {
        return poc >= v.size();
    }
    int size() {
        return v.size() - poc;
    }
};
Queue Q[4 * N];

int main() {
    scanf("%d", &n);
    for (int i = 0; i < n; i++) {
        scanf("%lld", &money[i]);
    }
    
    scanf("%d", &m);
    scanf("%s", state);
    for (int i = 0; i < m; i++) {
        state[i] = (state[i] == 'W'? 1: -1);
    }
    
    for (int i = 0; i < n; i++) {
        start[i % m].push_back(i); 
    }
    
    long long ans = 2e18;
    
    for (int i = 0; i < m; i++) {
        if (vis[i]) {
            continue;
        }
        
        long long endPosition = 0;
        long long endPrefSum = 0;
        long long mini = 0;
        
        int w = i;
        Q[C].push(0);
        do {
            endPrefSum += state[w];
            Q[endPrefSum + C].push(++endPosition);
            mini = min(mini, endPrefSum);
            w = (w + n) % m;
        } while (w != i);
        
        long long beginPrefSum = 0;
        long long beginPosition = 0;
        do {
            vis[w] = true;
            for (int j = 0; j < start[w].size(); j++) {
                long long currentMoney = money[start[w][j]];
                if (currentMoney <= -(mini - beginPrefSum)) {
                    long long numberOfSteps = Q[-currentMoney + beginPrefSum + C].front() - beginPosition;
                    ans = min(ans, start[w][j] + 1 + (long long)(numberOfSteps - 1) * n);
                } else if (endPrefSum - beginPrefSum >= 0) {
                    continue;
                } else {
                    long long newValue = currentMoney + (mini - beginPrefSum);
                    long long numberOfCycles = (newValue + beginPrefSum - endPrefSum - 1) / (beginPrefSum - endPrefSum);
                    long long totalDistance = start[w][j] + 1 + numberOfCycles * (endPosition - beginPosition) * n;
                    currentMoney += (long long)(endPrefSum - beginPrefSum) * numberOfCycles;
                    long long numberOfSteps = Q[-currentMoney + beginPrefSum + C].front() - beginPosition;
                    ans = min(ans, totalDistance + (long long)(numberOfSteps - 1) * n);
                }
            }
            beginPosition++;
            endPosition++;
            
            Q[beginPrefSum + C].pop();
            if (beginPrefSum == mini && Q[beginPrefSum + C].empty()) {
                mini++;
            }
            
            beginPrefSum += state[w];
            endPrefSum += state[w];
            
            Q[endPrefSum + C].push(endPosition);
            if (endPrefSum < mini) {
                mini = endPrefSum;
            }
            
            w = (w + n) % m;
        } while(w != i);
  
        do {
            Q[beginPrefSum + C].pop();
            beginPrefSum += state[w];
            w = (w + n) % m;
        } while(w != i);
        
        Q[beginPrefSum + C].pop();
    }
    
    if (ans == 2e18) {
        printf("-1\n");
    } else {
        printf("%lld\n", ans);
    }
    return 0;
}