Cho dãy \(A=(a_1,a_2,…,a_n )\) là một hoán vị của các số \(1…n\). Một xâu độ dài \(l\) chỉ gồm các chữ cái \(U,D\) được gọi là phù hợp với dãy \(A\) nếu tồn tại dãy con độ dài \(l+1\) của \(A\) thỏa mãn: với mọi \(i=1 \rightarrow l\), kí tự thứ \(i\) của xâu là \(U\) hay \(D\) tương ứng với phần tử thứ \(i\) của dãy con là nhỏ hơn hay lớn hơn phần tử thứ \(i+1\) của dãy con.
Cho xâu \(S\) độ dài \(n-1\) chỉ gồm các chữ cái \(U,D\), hãy xác định tiền tố dài nhất của \(S\) phù hợp với dãy \(A\).

Input

• Dòng 1: số nguyên \(n\) \((2 \leq n \leq 3⋅10^5 )\);
• Dòng 2: \(n\) số nguyên \(a_1,a_2,…,a_n\);
• Dòng 3: xâu \(S\).

Output

• Số nguyên là độ dài tiền tố dài nhất của \(S\) phù hợp với dãy \(A\).

Scoring

• Subtask \(1\) (\(10\%\) số điểm): \(n \leq 500\).
• Subtask \(2\) (\(20\%\) số điểm): \(n \leq 5000\) .
• Subtask \(3\) (\(20\%\) số điểm): \(S = UU ... UDD ... D\).
• Subtask \(4\) (\(50\%\) số điểm): Không có ràng buộc bổ sung.

Example

5
1 5 3 4 2
UDUD

4

5
1 5 3 4 2
UUDD

3