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

const int MAX_N = 1000009;
const int MAX_M = MAX_N;
const int OFF = MAX_M-1;
const long long INF = ((long long)MAX_M)*MAX_N*MAX_N;

int a[MAX_N];
char wins[MAX_M];
struct list {
  int num;
  list* prev;
  list* next;
};
list elem[MAX_N];
list* bl[MAX_M*2];
list* ab[MAX_M*2];
bool used[MAX_M];
bool checked[MAX_N];

void add(list*& head, list* elem) {
  if (!head) {
    head = elem;
  } else {
    elem->prev = head->prev;
    elem->next = head;
    head->prev->next = elem;
    head->prev = elem;
  }
}

void pop(list*& head) {
  if (!head)
    return;
  list* elem = head;
  if (elem->next == elem) {
    head = NULL;
  } else {
    head = elem->next;
    elem->next->prev = elem->prev;
    elem->prev->next = elem->next;
  }
}

int main() {
  int n, m;
  scanf("%d", &n);
  for (int i = 0; i < n; ++i)
    scanf("%d", &a[i]);
  scanf("%d", &m);
  scanf("%s", wins);
  long long min = INF;
  for (int i = 0; i < n; ++i) {
    if (used[i%m])
      continue;
    int rl = 0;
    int sum = 0;
    int max = 0;
    for (int cur = i%m; !used[cur]; cur = (cur+n)%m) {
      sum += (wins[cur] == 'P') ? 1 : -1;
      elem[rl] = {rl, &elem[rl], &elem[rl]};
      add(bl[OFF+sum], &elem[rl]);
      used[cur] = true;
      if (sum > max)
	max = sum;
      ++rl;
    }
    int psum = 0;
    int cur = i%m;
    for (int j = 0; j < rl; ++j) {
      for (int id = cur; id < n && !checked[id]; id += m) {
	// przegrywa przed końcem cyklu
	int tl = a[id];
	if (tl+psum < MAX_M && bl[OFF+tl+psum]) {
	  min = std::min(min, ((long long)bl[OFF+tl+psum]->num-j)*n+id+1);
	} else {
	  // dograj do końca cyklu
	  tl -= sum-psum;
	  // ile cykli musimy jeszcze rozegrać
	  int cycles = 0;
	  if (sum > 0 && tl > max) {
	    cycles = (tl-max+sum-1)/sum;
	  }
	  tl -= cycles*sum;
	  // gry = ile czekamy na kolejkę
	  long long games = id+1;
	  // + cykl dograny do końca
	  games += ((long long)rl-j)*n;
	  // + cykle które gramy całe
	  games += ((long long)rl)*n*cycles;
	  if (tl < MAX_M) {
	    if (ab[OFF+tl]) {
	      min = std::min(min, games+((long long)ab[OFF+tl]->num)*n);
	    } else if (bl[OFF+tl]) {
	      min = std::min(min, games+((long long)bl[OFF+tl]->num)*n);
	    }
	  }
	}
	checked[id] = true;
      }
      psum += (wins[cur] == 'P') ? 1 : -1;
      struct list* el = bl[OFF+psum];
      pop(bl[OFF+psum]);
      add(ab[OFF+psum], el);
      cur = (cur+n)%m;
    }
    for (int j = max-rl; j <= max; ++j) {
      bl[OFF+j] = ab[OFF+j] = NULL;
    }
  }
  if (min == INF) {
    printf("-1\n");
  } else {
    printf("%lld\n", min);
  }
}