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
//Przemysław Jakub Kozłowski
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <vector>
#define FI first
#define SE second
#define MP make_pair
using namespace std;
typedef long long LL;
const int N = 1000006, M = 1000006, INF = 1000000009;
const LL LINF = 1000000000000000018;

inline int dzsuf(int a, int b) {return (a+b-1)/b;}

int n,m;
int A[N];
char B[M];

int zaw[M];
int pelne[M];

int tab_[6*M+15];
int tab_ind, tab_war;
int *tab = tab_+3*M+7;

int main()
{
    scanf("%d", &n);
    for(int i = 1;i <= n;i++)
        scanf("%d", &A[i]);
    scanf("%d", &m);
    scanf(" ");
    for(int i = 1;i <= m;i++)
    {
        char c = getchar_unlocked();
        B[i] = (c == 'P' ? -1 : 1);
    }

    A[n+1] = INF;
    for(int i = 1;i <= m;i++) zaw[i] = n+1;
    for(int i = 1;i <= n;i++)
        if(A[zaw[(i-1)%m+1]] > A[i])
            zaw[(i-1)%m+1] = i;

    pair<LL, int> wyn = MP(LINF, INF);

    int cykle = __gcd(n, m);
    for(int cnr = 1;cnr <= cykle;cnr++)
    {
        vector<int> tcykl;
        for(int p = cnr;;)
        {
            tcykl.push_back(p);
            p = (p+n-1)%m+1;
            if(p == cnr) break;
        }

        tab_ind = 0;
        tab_war = 0;
        for(int i = -((int)tcykl.size()+5);i <= (int)tcykl.size()+5;i++) tab[i] = INF;

        int suma = 0, minimum = 0;
        tab[0] = 0;
        for(int i = 0;i < tcykl.size();i++)
        {
            suma += B[tcykl[i]];
            minimum = min(minimum, suma);
            tab[suma] = min(tab[suma], i+1);
        }

        for(int i = tcykl.size()-1;i >= 0;i--)
        {
            char znak = B[tcykl[i]];
            tab_war++;
            tab_ind += znak;
            tab[0-tab_ind] = 0-tab_war;

            if(tab[(minimum-1)-tab_ind]+tab_war <= tcykl.size()) minimum = minimum-1;
            else if(tab[minimum-tab_ind]+tab_war <= tcykl.size()) minimum = minimum;
            else minimum = minimum+1;

            int poczatkowe = A[zaw[tcykl[i]]];
            int pelne = -1;
            if(poczatkowe <= (-minimum)) pelne = 0;
            else if(suma < 0) pelne = dzsuf(max(0,poczatkowe-(-minimum)), -suma);
            if(pelne >= 0)
            {
                int zostanie = poczatkowe-pelne*(-suma);
                //cerr << "Zostanie: " << zostanie << endl;
                int dodatkowo = tab[(-zostanie)-tab_ind]+tab_war;
                LL twyn = (LL)pelne*tcykl.size()+dodatkowo;
                wyn = min(wyn, MP(twyn, zaw[tcykl[i]]));
            }
        }
    }

    if(wyn.FI == LINF) printf("-1\n");
    else
    {
        LL Kwyn = (wyn.FI-1)*n+wyn.SE;
        printf("%lld\n", Kwyn);
    }
    return 0;
}