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$ 的最大可能值。

样例

样例输入 1

5
1 5 3 4 2
UDUD

样例输出 1

4

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

样例输入 2

5
1 5 3 4 2
UUDD

样例输出 2

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