У Фермера Джона є \(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.

Формат вхідних даних

Перший рядок містить \(N\).

Другий рядок містить перестановку \(p_1,p_2,\ldots,p_N\).

Останній рядок містить рядок.

Формат вихідних даних

Виведіть максимально можливе значення \(K\).

Приклад вхідних даних

5
1 5 3 4 2
UDUD

Приклад вихідних даних

4

Ми можемо вибрати \([a_0,a_1,a_2,a_3,a_4]=[p_1,p_2,p_3,p_4,p_5]\); вся перестановка відповідає рядку.

Приклад вхідних даних

5
1 5 3 4 2
UUDD

Приклад вихідних даних

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 немає додаткових обмежень.