Cho một dãy ~N~ số nguyên ~A = \{a_1, a_2,\ldots, a_n\}~. Dãy răng cưa là dãy thỏa tính chất sau: ~a_1 < a_2 > a_3 <a_4 \ldots~ hoặc ~a_1 > a_2 <a_3 >a_4 \ldots~.

Hãy lập trình giúp Bi xác định dãy số trên có phải là dãy răng cưa hay không?

Input

Dòng đầu tiên chứa số nguyên dương ~n~ thỏa ~3 \le n \le 10^5~.

Dòng tiếp theo chứa các số nguyên ~a_i~ thỏa ~1 \le a_i \le 10^9~.

Output

In ra Yes nếu thỏa và No nếu ngược lại.

Samples

Sample Input 1

3 
4 1 5

Sample Output 1

Yes

Sample Input 2

3 
1 4 1

Sample Output 2

Yes