У Фермера Джона имеется \(N\) коров (\(2 \leq N \leq 3\cdot 10^5\)), последовательно
пронумерованных 1 \ldots N$, упорядоченных в соответствии с перестановкой
\(p_1,p_2,\ldots,p_N\) of \(1\ldots N\). Также дана строка длины \(N-1\),
состоящая из символов U и D.
Определите максимальное \(K\le N-1\) такое, что существует подпоследовательность
subsequence \(a_0,a_1,\ldots,a_{K}\) чисел \(p\) таких, что для всех \(1\le j\le K\), \(a_{j - 1} < a_j\)
если j-ый символ в строке есть U, и \(a_{j - 1} > a_j\), если \(j\)-ый символ в строке есть D.
ФОРМАТ ВВОДА (с клавиатуры / stdin):
Первая строка содержит
\(N\).
Вторая строка содержит перестановку \(p_1,p_2,\ldots,p_N\).
Последняя строка содержит строку.
ФОРМАТ ВЫВОДА (на экран / stdout):
Выведите максимально возможное значение \(K\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
5
1 5 3 4 2
UDUD
|
4
|