【问题描述】

Farmer John 的 N 头奶牛（2≤N≤3⋅10^5），编号为 1…N，排列成 1…N 的一个排列 p1,p2,…,pN。另外给定一个长为 N−1 的字符串，由字母 U 和 D 组成。

请求出最大的 K≤N−1，使得存在 p 的一个子序列 a0,a1,…,aK，满足对于所有 1≤j≤K，当字符串中第 j 个字母是 U 时 aj−1<aj，当字符串中的第 j 个字母是 D 时 aj−1>aj。

【输入格式】

输入的第一行包含 N。

第二行包含 p1,p2,…,pN。

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

【输出格式】

输出 K 的最大可能值。

【输入样例】

5
1 5 3 4 2
UDUD

【输出样例】

4

我们可以选择 [a0,a1,a2,a3,a4]=[p1,p2,p3,p4,p5]；整个排列与给定的字符串相一致。

【输入样例】

5
1 5 3 4 2
UUDD

【输出样例】

3

我们可以选择 [a0,a1,a2,a3]=[p1,p3,p4,p5]。

测试点性质：

测试点 3-4 满足 N≤500。

测试点 5-8 满足 N≤5000。

测试点 9-12 中，字符串中的 U 均在 D 之前。

测试点 13-22 没有额外限制。

供题：Danny Mittal