Problem 3. Up Down Subsequence

USACO 2022 US Open Contest, Platinum

Farmer John 的 $N$ 头奶牛（$2 \leq N \leq 3\cdot 10^5$），编号为 $1 \ldots N$，排列成 $1\ldots N$ 的一个排列 $p_1,p_2,\ldots,p_N$。另外给定一个长为 $N-1$ 的字符串，由字母 U 和 D 组成。请求出最大的 $K\le N-1$，使得存在 $p$ 的一个子序列 $a_0,a_1,\ldots,a_{K}$，满足对于所有 $1\le j\le K$，当字符串中第 $j$ 个字母是 U 时 $a_{j - 1} < a_j$，当字符串中的第 $j$ 个字母是 D 时 $a_{j - 1} > a_j$。

输入格式（从终端 / 标准输入读入）：

输入的第一行包含 $N$。

第二行包含 $p_1,p_2,\ldots,p_N$。

最后一行包含给定的字符串。

输出格式（输出至终端 / 标准输出）：

输出 $K$ 的最大可能值。

输入样例：

5
1 5 3 4 2
UDUD

输出样例：

4

我们可以选择 $[a_0,a_1,a_2,a_3,a_4]=[p_1,p_2,p_3,p_4,p_5]$；整个排列与给定的字符串相一致。

输入样例：

5
1 5 3 4 2
UUDD

输出样例：

3

我们可以选择 $[a_0,a_1,a_2,a_3]=[p_1,p_3,p_4,p_5]$。

测试点性质： 测试点 3-4 满足 $N\le 500$。测试点 5-8 满足 $N\le 5000$。测试点 9-12 中，字符串中的 U 均在 D 之前。测试点 13-22 没有额外限制。

供题：Danny Mittal