Up Down Subsequence

문제

Farmer John's $NN$ cows ($2\le N\le 3\cdot {10}^{5}2\; \backslash leq\; N\; \backslash leq\; 3\backslash cdot\; 10^5$), conveniently numbered $1\dots N1\; \backslash ldots\; N$ as usual, have ordered themselves according to a permutation $p_1,p_2,\dots ,p_{N}p\_1,p\_2,\backslash ldots,p\_N$ of $1\dots N1\backslash ldots\; N$. You are also given a string of length $N-1N-1$ consisting of the letters U and D. Please find the maximum $K\le N-1K\backslash le\; N-1$ such that there exists a subsequence $a_0,a_1,\dots ,a_{K}a\_0,a\_1,\backslash ldots,a\_\{K\}$ of $pp$ such that for all $1\le j\le K1\backslash le\; j\backslash le\; K$, if the $jj$th letter in the string is U, and $a_{j-1}>a_{j}a\_\{j\; -\; 1\}\; >\; a\_j$ if the $jj$th letter in the string is D.

입력

The first line contains $NN$.

The second line contains $p_1,p_2,\dots ,p_{N}p\_1,p\_2,\backslash ldots,p\_N$.

The last line contains the string.

출력

Write out maximum possible value of $KK$.