Ga trung chuyển một đường ray

Bối cảnh và bài toán

Các toa tàu đi vào ga theo thứ tự 1,2,...,n. Ga có một đường ray phụ dạng ngăn xếp: toa vào sau phải ra trước. Mỗi toa có thể đi thẳng ra hoặc được đưa vào ray phụ rồi lấy ra sau. Người vận hành muốn tạo một thứ tự đầu ra cho trước.

Yêu cầu

Xác định có thể tạo đúng hoán vị mục tiêu hay không.

Input

• Dòng 1: n.
• Dòng 2: hoán vị p[1..n].

Output

In YES nếu thực hiện được, ngược lại in NO.

Ràng buộc

• 1 <= n <= 2 * 10^5
• p là hoán vị của 1..n

Chấm điểm

Ví dụ 1

Input

5
5 4 3 2 1

Output

YES

Giải thích. Đưa toàn bộ toa 1..5 vào ray phụ rồi lấy ra ngược lại.

Ví dụ 2

Input

5
3 1 2 5 4

Output

NO

Giải thích. Sau khi đưa 1,2,3 vào và lấy 3 ra, toa 2 nằm trên toa 1 nên không thể lấy 1 trước 2.

Thông tin bài tập

Nguồn: Phỏng theo UVa Online Judge 514 – Rails.

Tham khảo: https://onlinejudge.org/external/5/514.pdf