Dãy Tăng Giảm

Farmer John có $N$ con bò ($2\le N\le 3\times {10}^5$), được đánh số từ $1$ đến $N$, xếp thành một hoán vị $p_1,p_2,\dots ,p_N$ của các số từ $1$ đến $N$.

Cho một xâu độ dài $N-1$ chỉ gồm các ký tự U (tăng) và D (giảm). Hãy tìm giá trị $K$ lớn nhất ($K\le N-1$) sao cho tồn tại một dãy con $a_0,a_1,\dots ,a_K$ của $p$ (tức là chọn $K+1$ phần tử theo đúng thứ tự trong $p$) thỏa mãn:

• Với mỗi $j$ từ $1$ đến $K$: nếu ký tự thứ $j$ của xâu là U thì $a_{j-1}<a_j$, nếu là D thì $a_{j-1}>a_j$.

Dữ liệu vào

• Dòng 1: Số nguyên $N$.
• Dòng 2: $N$ số nguyên phân biệt $p_1,p_2,\dots ,p_N$ — một hoán vị của $1\dots N$.
• Dòng 3: Xâu độ dài $N-1$ gồm các ký tự U và D.

Dữ liệu ra

Một số nguyên duy nhất — giá trị $K$ lớn nhất tìm được.

Ràng buộc

• $2\le N\le 3\times {10}^5$
• $p$ là hoán vị của $1\dots N$
• Xâu có độ dài $N-1$ và chỉ chứa U, D

Subtask:

• Subtask 1 (9%): $N\le 500$
• Subtask 2 (18%): $N\le 5000$
• Subtask 3 (18%): Xâu gồm các ký tự U rồi đến các ký tự D (có thể không có phần nào)
• Subtask 4 (55%): Không có ràng buộc thêm

Ví dụ

Ghi chú

Trong ví dụ 2, xâu UUDD có độ dài 4 nhưng không thể đạt $K=4$ (sẽ cần dãy con độ dài 5 thỏa mãn UUDD, nhưng không tồn tại dãy con như vậy trong $p$).