Problem
Bắt buộc để xác định xem có thể sắp xếp một dãy số bằng ngăn xếp hay không.
Một đoàn tàu đã đến ngõ cụt từ đường ray 1 (xem hình). Được phép tháo một hoặc một số toa đầu tiên ra khỏi đoàn tàu cùng một lúc và đưa chúng vào ngõ cụt (nếu muốn, bạn thậm chí có thể đưa cả đoàn tàu vào ngõ cụt cùng một lúc). Sau đó, đưa một số toa xe vào lề đường 2. Sau đó, bạn có thể đưa thêm một số toa xe vào ngõ cụt, và lại vận chuyển một phần toa xe sang lề đường 2. Và cứ như vậy, sao cho mỗi toa xe chỉ lái xe từ đường 1 đến ngõ cụt một lần, sau đó một lần rời khỏi ngõ cụt trên đường 2. Đi vào ngõ cụt từ đường 2 hoặc rời khỏi ngõ cụt trên đường 1 đều bị cấm. Bạn không thể đi từ đường 1 đến đường 2 mà không đi vào ngõ cụt.
Đã biết ban đầu các toa tàu đi theo thứ tự nào. Sử dụng các thao tác đã chỉ định, cần phải làm cho các toa tàu đi theo thứ tự (toa thứ nhất, sau đó là toa thứ hai, v.v., tính từ đầu tàu đi dọc theo đường 2 ra khỏi ngõ cụt). Viết chương trình để xác định xem có thể thực hiện được không.
Đầu vào
Nhập số N — số toa trong đoàn tàu (\(1<=N<=2000\)). Tiếp đến là các toa số theo thứ tự từ đầu tàu đi trên đường số 1 về phía đường cụt. Ô tô được đánh số tự nhiên từ 1 đến N, mỗi số xuất hiện đúng một lần.
Đầu ra
Có thể cho các toa đi theo thứ tự từ 1 đến N, tính từ đầu đoàn tàu, khi đoàn tàu đi theo đường 2 từ ngõ cụt không? Nếu có thể, hãy hiển thị thông báo YES. Nếu không thể, hãy in NO.
Ví dụ
<đầu>
| # |
Đầu vào |
Đầu ra |
Lưu ý |
| 1 |
3
3 2 1
| CÓ |
Chúng ta cần đưa toàn bộ đoàn tàu vào ngõ cụt, sau đó đưa toàn bộ sang đường ray thứ 2 |
| 2 |
4
4 1 3 2
|
CÓ
|
Đầu tiên, bạn cần đưa hai toa xe vào ngõ cụt, một trong số đó sẽ bị bỏ lại trong ngõ cụt và toa thứ hai — đưa ra đường thứ 2, sau đó đưa thêm 2 xe vào ngõ cụt và đưa 3 xe đang đứng ở ngõ cụt vào đường thứ 2 |
| 3 |
3
2 3 1
| KHÔNG |
|