8161: USACO 2022 US Open Contest, Platinum Problem 3. Up Down Subsequence
[Creator : ]
Description
Farmer John's N cows $(2≤N≤3⋅10^5)$, conveniently numbered 1…N as usual, have ordered themselves according to a permutation $p_1,p_2,…,p_N$ 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 $a_0,a_1,…,a_K$ of p such that for all $1≤j≤K, a_{j−1}<a_j$ if the j-th letter in the string is U, and $a_{j−1}>a_j$ if the j-th letter in the string is D.
Input
The first line contains N.
The second line contains $p_1,p_2,…,p_N$.
The last line contains the string.
The last line contains the string.
Output
Write out maximum possible value of K.
Sample 1 Input
5
1 5 3 4 2
UDUD
Sample 1 Output
4
We can choose $[a_0,a_1,a_2,a_3,a_4]=[p_1,p_2,p_3,p_4,p_5]$; the entire permutation is consistent with the string.
Sample 2 Input
5
1 5 3 4 2
UUDD
Sample 2 Output
3
We can choose $[a_0,a_1,a_2,a_3]=[p_1,p_3,p_4,p_5]$.