U219986 [USACO 2022 US Open Contest, P, P3] 向上向下子序列

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

输入的第一行包含 $N$。 第二行包含 $p_1,p_2,…,p_N$。 最后一行包含给定的字符串。

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

【数据范围】 $2\le N\le3\times10^5$。 【测试点性质】 - 测试点 3-4 满足 $N\le500$。 - 测试点 5-8 满足 $N\le5000$。 - 测试点 9-12 中，字符串中的 `U` 均在 `D` 之前。 - 测试点 13-22 没有额外限制。 【样例说明】 #### 样例组 #1 我们可以选择 $[a_0,a_1,a_2,a_3]=[p_1,p_3,p_4,p_5]$。