Chơi bi da 1 lỗ

Tác giả:

Dạng bài

Điểm: 1200 (p) Thời gian: 1.0s Bộ nhớ: 256M Input: bàn phím Output: màn hình

Mike chơi bi-a 1 lỗ rất giỏi nên kiếm được rất nhiều tiền độ banh. Nhà Cái mất nhiều tiền vì Mike lắm nên cú lắm nên họ quyết phải kiểm tra xem liệu Mike có chơi gian hay không?

Thể thức chơi bi-a 1 lỗ là như này: Có \(N\) viên bi được đánh số từ \(1 \rightarrow N\), đặt trên bàn, người chơi phải đánh sao cho các viên bi này lọt lỗ theo đúng thứ tự từ \(1 \rightarrow N\). Viên \(I\) sẽ phải vào lỗ trước viên \(i+1\). Để kiểm tra Mike, nhà Cái thuê 1 tay thám tử. Tay thám tử này sẽ kiểm tra bằng cách là thỉnh thoảng lại tiến lại cái lỗ và bốc lên viên ở trên cùng trong lỗ. Sau khi Mike đã đánh hết các bi vào lỗ rồi thì thám tử sẽ bốc hết các viên ở trong lỗ ra từ viên trên cùng tới viên dưới cùng. Hãy giúp thám tử xác định xem liệu Mike có chơi gian không? (Xem test ví dụ để hiểu rõ hơn).

Input

Dòng đầu tiên chứa 1 số nguyên dương \(N\) \((N \leq 10^5)\).
\(N\) dòng tiếp theo mỗi dòng gồm 1 số nguyên ghi ra số chỉ trên trái bi mà thám tử lần lượt bốc lên được.

Output

Nếu xác định được Mike chơi gian thì ghi ra YES, ngược lại ghi NO.

Example

Test 1

Input

Output

YES

Test 2

Input

Output

NO

Note

Ở test ví dụ 1: Khi thám tử bốc được bi số 3 lên thì có nghĩa là bi số 1, 2 đã vào lỗ rồi. Và như vậy bi trên cùng sau khi bốc bi số 3 ra phải là bi số 2 nhưng thám tử lại bốc ra được bi số 1 ⇒ vô lý ⇒ Mike đã ăn gian.
Ở test ví dụ 2: Có thể xảy ra trường hợp thám tử bốc viên bi 1, 3, 5 ngay khi Mike vừa đánh chúng vào lỗ. Sau đó thám tử bốc những viên bi còn lại. Do đó không khẳng định được Mike đã ăn gian!

Bình luận

Không có bình luận nào.