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
import java.io.*;
import java.util.*;


public class haz {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int boysCount = Integer.parseInt(br.readLine());
        int[] boys = new int[boysCount];
        String boysString = br.readLine()+' ';
        int prevIdx = 0;
        for (int j = 0; j < boysCount; j++) {
            int idx =  boysString.indexOf(' ', prevIdx);
            boys[j] = Integer.parseInt(boysString.substring(prevIdx, idx));
            prevIdx = idx+1;
        }
        int cycleLength = Integer.parseInt(br.readLine());
        int[] cycle = new int[cycleLength];
        for (int j = 0; j < cycle.length; j++) {
            if (br.read() == 'W') {
                cycle[j] = 1;
            } else {
                cycle[j]= -1;
            }
        }

        int queueLen = (int) (nww(boysCount, cycleLength) / boysCount);

        int differentCyclesForBoys = cycleLength / queueLen;
        int[][] queuesForBoys = new int[differentCyclesForBoys][queueLen];
        List<Integer>[][] queuesForBoysIdx = new List[differentCyclesForBoys][];
        int[][] queuesForBoysAccum = new int[differentCyclesForBoys][cycleLength / differentCyclesForBoys];
        int[] offsets = new int[cycleLength];
        for (int j = 0; j < differentCyclesForBoys; j++) {
            for (int k = 0; k < queueLen; k++) {
                int value = (int) ((j + (long) k * boysCount) % cycleLength);
                queuesForBoys[j][k] = cycle[value];
                offsets[value] = k;
            }
        }

        for (int j = 0; j < differentCyclesForBoys; j++) {
            int[] queue = queuesForBoys[j];

            int[] queueAccu = new int[queue.length];
            queueAccu[0] = queue[0];
            int maxDrop = 0;
            for (int k = 1; k < queue.length; k++) {
                queueAccu[k] = queueAccu[k - 1] + queue[k];
                maxDrop = Math.max(maxDrop, -queueAccu[k]);
            }
            List<Integer>[] queueIndex = new ArrayList[maxDrop + 1];
            for (int k = 0; k < queueAccu.length; k++) {
                int drop = -queueAccu[k];
                if (drop <= 0) continue;
                List<Integer> indexes = queueIndex[drop];
                if (indexes == null) {
                    indexes = new ArrayList<>();
                    queueIndex[-queueAccu[k]] = indexes;
                }
                indexes.add(k);
            }
            queuesForBoysIdx[j] = queueIndex;
            queuesForBoysAccum[j] = queueAccu;
        }

        long firstBancrupt = -1;
        long firstBancruptRounds = Long.MAX_VALUE;
        for (int j = 0; j < boysCount; j++) {
            int mod = j % differentCyclesForBoys;

            int offset = offsets[j % cycleLength];
            long roundsToBancrupt = roundsForBoy(queuesForBoysIdx[mod], boys[j], queuesForBoysAccum[mod], offset);
            if (roundsToBancrupt != -1 && roundsToBancrupt < firstBancruptRounds) {
                firstBancruptRounds = roundsToBancrupt;
                firstBancrupt = j + 1;
            }
        }

        if (firstBancrupt == -1) {
            System.out.println("-1");
        } else {
            long result = (firstBancruptRounds - 1) * boysCount + firstBancrupt;
            System.out.println(result);
        }

    }


    static long roundsForBoy(List<Integer>[] queueIndex, int start, int[] queueAccumulated, int offset) {
        if (offset == 0) return roundsForBoy(queueIndex, start, queueAccumulated);
        int offsetValue = queueAccumulated[offset - 1];
        int maxDrop = queueIndex.length - 1;
        if (start - offsetValue <= maxDrop) {
            List<Integer> indexes = queueIndex[start - offsetValue];
            int firstGeq = firstGeq(indexes, offset);
            if (firstGeq >= 0 ) {
                return firstGeq - offset + 1;
            }
        }
        int newStart = start - offsetValue + queueAccumulated[queueAccumulated.length - 1];
        long roundsForNewStart = roundsForBoy(queueIndex, newStart, queueAccumulated);
        if (roundsForNewStart == -1) {
            return -1;
        } else {
            return queueAccumulated.length - offset + roundsForNewStart;
        }
    }

    static long roundsForBoy(List<Integer>[] queueIndex, int start, int[] queueAccumulated) {
        int queueSum = queueAccumulated[queueAccumulated.length - 1];
        int maxDrop = queueIndex.length - 1;
        if (start <= maxDrop) {
            return queueIndex[start].get(0) + 1;
        } else if (queueSum >= 0) {
            return -1;
        } else {
            int fullCycles = (int) Math.ceil(((float) start - maxDrop) / -queueSum);
            int remaining = start + fullCycles * queueSum;
            return queueIndex[remaining].get(0) + 1L + (long)queueAccumulated.length * fullCycles;
        }
    }


    static int nwd(int a, int b) {
        if (b == 0)
            return a;
        else
            return nwd(b, a % b);
    }

    static long nww(int a, int b) {
        return ((long) a * b) / nwd(a, b);
    }

    static int firstGeq(List<Integer> list, int element) {
        int ins =  Collections.binarySearch(list,element);
        if (ins >= 0) {
            return list.get(ins);
        } else if (ins == -list.size() - 1) {
            return -1;
        } else {
            return list.get(-ins-1);
        }
    }
}