Nông dân John có \(N\) con bò \((2 \le N \le 3 \times 10^5)\) được đánh số từ \(1\) đến \(N\) như thường lệ. Những chú bò này đã xếp hàng thành một hoán vị \(p_1, p_2, \dots, p_N\). Bạn được cho một chuỗi dài \(N - 1\) chỉ bao gồm kí tự U và D. Hãy tìm ra số \(K \le N - 1\) lớn nhất sao cho tồn tại đãy con \(a_0, a_1, \dots, a_K\) của \(p\) thoả mãn với mọi \(1 \le j \le K, a_{j - 1} < a{j}\) nếu kí tự thứ \(j\) trong chuỗi là U và \(a_{j - 1} > a{j}\) nếu kí tự thứ \(j\) trong chuỗi là D.

Input

• Dòng đầu tiên là số \(N\).
• Dòng tiếp theo là các số \(p_1, p_2, \dots, p_N\).
• Dòng cuối cùng là chuỗi được cho.

Output

• Số \(K\) thoả mãn.

Scoring

• Subtask \(1\): \(N \le 500\).
• Subtask \(2\): \(N \le 5000\).
• Subtask \(3\): Phần đầu của chuỗi chỉ toàn kí tự U sau đó chỉ toàn kí tự D.
• Subtask \(4\): Không có thêm ràng buộc.

5
1 5 3 4 2
UDUD

4

5
1 5 3 4 2
UUDD

3