TDZ đang có ước mơ làm một kiến trúc sư. Chính vì vậy, cậu đã mua một con robot giúp cậu xây tháp bằng các miếng gỗ theo bản thiết kế của cậu.

Toà tháp theo thiết kế của TDZ là tập hợp gồm ~n~ cột gỗ với các độ cao khác nhau. Robot xây tháp có thể thực hiện một trong hai lệnh sau khi TDZ đưa cho robot một số ~i~:

• Robot sẽ đi từ trái sang phải từ cột ~1~ đến cột ~i~, đồng thời xếp ~1~ miếng gỗ lên lần lượt các cột gỗ đã đi qua.
• Robot sẽ đi từ phải sang trái từ cột ~n~ đến cột ~i~, đồng thời xếp ~1~ miếng gỗ lên lần lượt các cột gỗ đã đi qua.

Con robot của TDZ thuộc loại hàng xịn nên có thể chạy liên tục không hết pin và có thể thực hiện các lệnh khác nhau vô số lần. Sau một hồi thử nghiệm, TDZ nhận ra rằng không phải lúc nào robot cũng xây được tháp theo như bản thiết kế của cậu. Là bạn thân của TDZ, hãy giúp TDZ xác định xem bản thiết kế nào của cậu thì robot có thể xây được nhé.

Input

• Dòng đầu tiên gồm một số nguyên dương ~n~ (~n \leq 10^6~).
• Dòng tiếp theo gồm ~n~ số nguyên mô tả độ cao của các cột trong bản thiết kế. Độ cao các cột không vượt quá ~10^9~ miếng gỗ.

Output

In ra YES nếu robot có thể xây tháp theo bản thiết kế đã cho, ngược lại in ra NO.

Sample Test 1

Input:

4 
1 3 2 4

Output:

YES

Note: Có thể ra lệnh cho robot:

• Đi từ trái sang phải đến cột thứ hai ~1~ lần.
• Đi từ phải sang trái đến cột thứ hai ~2~ lần.
• Đi từ phải sang trái đến cột thứ tư ~2~ lần.

Sample Test 2

Input:

4
1 0 3 2

Output:

NO