#include #include #include using namespace std; struct charSet{ int base = 2; int encode(char c){ return (c == '<' ? 0 : 1); } }; struct RollingHash{ charSet C; string t; const long long MOD1 = 1000000007; const long long MOD2 = 998244353; vector stringIdx[1000001]; map, int> hashIdx; int idxSize; RollingHash(string s, int n){ idxSize = 0; long long val1 = 0; long long val2 = 0; long long baseMOD1 = 1; long long baseMOD2 = 1; for(int i = 0; n > i; i++){ baseMOD1 = (baseMOD1*C.base)%MOD1; baseMOD2 = (baseMOD2*C.base)%MOD2; val1 = (val1*C.base + C.encode(s[i]))%MOD1; val2 = (val2*C.base + C.encode(s[i]))%MOD2; } for(int i = n; s.size() >= i; i++){ if(!hashIdx[make_pair(val1, val2)]){ hashIdx[make_pair(val1, val2)] = hashIdx.size(); } stringIdx[hashIdx[make_pair(val1, val2)]].push_back(i-n); if(i!=s.size()){ val1 = ((val1*C.base + C.encode(s[i]))%MOD1 - (baseMOD1 * C.encode(s[i-n]))%MOD1 + MOD1)%MOD1; val2 = ((val2*C.base + C.encode(s[i]))%MOD2 - (baseMOD2 * C.encode(s[i-n]))%MOD2 + MOD2)%MOD2; } } idxSize = hashIdx.size(); } RollingHash(string s, string x): RollingHash(s, (int)x.size()){ t = x; } pair hash(string x){ long long val1 = 0; long long val2 = 0; for(int i = 0; x.size() > i; i++){ val1 = (val1*C.base + C.encode(x[i]))%MOD1; val2 = (val2*C.base + C.encode(x[i]))%MOD2; } return make_pair(val1, val2); } vector search(){ return search(t); } vector search(string x){ auto hashedString = hash(x); return stringIdx[hashIdx[hashedString]]; } int distMax(){ int distMx = 0; for(int i = 1; idxSize >= i; i++){ distMx = max(distMx, stringIdx[i][stringIdx[i].size()-1]-stringIdx[i][0]); } return distMx; } }; int main(){ int n;cin>>n; vector A(n); for(int i = 0; n > i; i++){ cin>>A[i]; } string c = ""; for(int i = 0; 2*n > i;i++){ c.push_back((A[(i)%n] < A[(i+1)%n] ? '<' : '>')); } string s;cin>>s; RollingHash B(c, n-1); auto z = B.search(s); if(z.size()){ cout << z[0] << endl; }else{ cout << -1 << endl; } }