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
#include <stdio.h>
#include <algorithm>
#include <limits.h>

typedef long long int ll;

using namespace std;

int n, m;

int boy[1000005];
int cycle[1000005];  //1 - win, -1 - lose

int loop[1000005];
int cycle_sum[1000005];
int cycle_size[1000005];

int main() {
    char inp;
    scanf("%d", &n);
    for (int i=0; i<n; ++i) {
        scanf("%d", boy+i);
    }
    scanf("%d\n", &m);
    for (int i=0; i<m; ++i) {
        scanf("%c", &inp);
        if (inp == 'W') {
            cycle[i] = 1;
        } else {
            cycle[i] = -1;
        }
    }

    for (int i=0; i<m; ++i) {
        loop[i] = (i + n) % m;
    }

    for (int i=0; i<m; ++i) {
        if (cycle_size[i] == 0) {
            int result = 0;
            int idx = i;
            int sx = 0;
            do {
                result += cycle[idx];
                idx = loop[idx];
                sx += 1;
            } while (idx != i);
            cycle_sum[i] = result;
            cycle_size[i] = sx;

            idx = i;
            do {
                idx = loop[idx];
                cycle_sum[idx] = result;
                cycle_size[idx] = sx;
            } while (idx != i);
        }
    }


    bool found = false;
    ll result = LONG_LONG_MAX;

    for (int i=0; i<n; ++i) {
        int current_cycle = i % m;
        int current_game = i;

        do {
//            printf("LOOP cycle=%d game=%d boy=%d money=%d sum=-%d diff=%d\n", current_cycle, current_game, i, boy[i], cycle_sum[current_cycle], cycle[current_cycle]);
            boy[i] += cycle[current_cycle];

            if (boy[i] <= 0) {
                result = min(result, (ll)current_game);
//                printf("DBG11 %d %d %d\n", i, current_cycle, current_game);
                found = true;
                break;
            }

            if (cycle_sum[current_cycle] < 0) {
                if (boy[i] % (-cycle_sum[current_cycle]) == 0) {
                    ll expected_loss = current_game + (ll)(boy[i] / (-cycle_sum[current_cycle])) * n * cycle_size[current_cycle];
                    result = min(result, expected_loss);
//                    printf("!!!DBG22 %d %d %d %lld\n", i, boy[i], cycle_sum[current_cycle], expected_loss);
                    found = true;
                }
            }

            current_cycle = loop[current_cycle];
            current_game += n;
        } while (current_cycle != (i % m));
    }

    if (!found) {
        printf("-1\n");
    } else {
        printf("%lld\n", result + 1);
    }

    return 0;
}