Farmer John's N cows (2≤N≤3⋅105), conveniently numbered 1…N as usual, have ordered themselves according to a permutation p1,p2,…,pN of 1…N. You are also given a string of length N−1 consisting of the letters U and D. Please find the maximum K≤N−1 such that there exists a subsequence a0,a1,…,aK of p such that for all 1≤j≤K, aj−1<aj if the jth letter in the string is U, and aj−1>aj if the jth letter in the string is D.
Input Format
The first line contains N.
The second line contains p1,p2,…,pN.
The last line contains the string.
Output Format
Write out maximum possible value of K.
Sample Input
5
1 5 3 4 2
UDUD
Sample Output
4
We can choose [a0,a1,a2,a3,a4]=[p1,p2,p3,p4,p5]; the entire permutation is consistent with the string.
Sample Input
5
1 5 3 4 2
UUDD
Sample Output
3
We can choose [a0,a1,a2,a3]=[p1,p3,p4,p5].
Scoring
- Test cases 3-4 satisfy N≤500.
- Test cases 5-8 satisfy N≤5000.
- In test cases 9-12, the string consists of Us followed by Ds.
- Test cases 13-22 satisfy no additional constraints.
Problem credits: Danny Mittal