Tý được cho một cây nhị phân với \(N\) nút, mỗi nút chứa một số nguyên. Tý cần xác định xem cây nhị phân này có phải là một cây tìm kiếm nhị phân (BST) hợp lệ hay không.

Một cây nhị phân được gọi là BST hợp lệ nếu:

• Cây con trái của một nút chỉ chứa các nút có giá trị nhỏ hơn nút đó.
• Cây con phải của một nút chỉ chứa các nút có giá trị lớn hơn nút đó.
• Cả hai cây con trái và phải cũng phải là BST.

Hãy giúp Tý viết chương trình kiểm tra tính hợp lệ của cây nhị phân.

Định dạng đầu vào

• Dòng đầu chứa số nguyên dương \(N\) (\(1 \le N \le 10^3\)).
• Dòng thứ hai chứa \(N\) số nguyên \(v_1, v_2, \dots, v_N\) là giá trị của các nút (\(1 \le v_i \le 10^9\)).
• \(N-1\) dòng tiếp theo, mỗi dòng chứa hai số nguyên \(u\) và \(v\) và một ký tự \(c\), cho biết nút \(v\) là con trái (nếu \(c = L\)) hoặc con phải (nếu \(c = R\)) của nút \(u\). Các nút được đánh số từ \(1\) đến \(N\), nút \(1\) là gốc.

Định dạng đầu ra

• In ra \(YES\) nếu cây là BST hợp lệ, ngược lại in ra \(NO\).

Ví dụ

Input:

5
5 3 7 2 6
1 2 L
1 3 R
2 4 L
2 5 R

Output:

NO

Giải thích: Nút \(5\) (con phải của nút \(2\)) có giá trị \(6\), lớn hơn nút \(3\) (con trái của nút \(1\)). Tuy nhiên vì nút \(3\) nằm ở cây con trái của gốc \(5\) nên giá trị \(6\) không được phép lớn hơn \(5\).