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 (input arrives from the terminal / stdin):
The first line contains N.
The second line contains p1,p2,…,pN.
The last line contains the string.
OUTPUT FORMAT (print output to the terminal / stdout):
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