【题目描述】

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，当字符串中的第 jj 个字母是 D 时 aj−1>ajaj−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 没有额外限制。