Up Down Subsequence | Code Joint

Farmer John's $N$ cows ( $2 \leq N \leq 3 \cdot 1 0^{5}$ ), conveniently numbered $1 \dots N$ as usual, have ordered themselves according to a permutation $p_{1}, p_{2}, \dots, p_{N}$ of $1 \dots N$ . You are also given a string of length $N - 1$ consisting of the letters U and D. Please find the maximum $K \leq N - 1$ such that there exists a subsequence $a_{0}, a_{1}, \dots, a_{K}$ of $p$ such that for all $1 \leq j \leq 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.

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.

We can choose $[a_{0}, a_{1}, a_{2}, a_{3}] = [p_{1}, p_{3}, p_{4}, p_{5}]$ .

SCORING:

Test cases 3-4 satisfy $N \leq 500$ .
Test cases 5-8 satisfy $N \leq 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

Source: USA Computing Olympiad.

Input Format

The first line contains $N$ .

The second line contains $p_{1}, p_{2}, \dots, p_{N}$ .

The last line contains the string.

Output Format

Write out maximum possible value of $K$ .

Sample Input 1

5 1 5 3 4 2 UDUD

Sample Output 1

4

Sample Input 2

5 1 5 3 4 2 UUDD

Sample Output 2

3

Submit

Language