Dãy răng cưa

Time limit: 1.0s , Memory limit: 256M , Points: 1 (partial)

Cho một dãy $N$ $N$ số nguyên $A = \{a_1, a_2,\ldots, a_n\}$ $A = {a_{1}, a_{2}, \dots, 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$ $a_{1} < a_{2} > a_{3} < a_{4} \dots$ hoặc $a_1 > a_2 <a_3 >a_4 \ldots$ $a_{1} > a_{2} < a_{3} > a_{4} \dots$ .

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$ $n$ thỏa $3 \le n \le 10^5$ $3 \leq n \leq 10^{5}$ .

Dòng tiếp theo chứa các số nguyên $a_i$ $a_{i}$ thỏa $1 \le a_i \le 10^9$ $1 \leq a_{i} \leq 10^{9}$ .

Output

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

Samples

Sample Input 1

Copy

3 
4 1 5

Sample Output 1

Copy

Yes

Sample Input 2

Copy

3 
1 4 1

Sample Output 2

Copy

Yes

Dãy răng cưa

Input

Output

Samples

Sample Input 1

Sample Output 1

Sample Input 2

Sample Output 2

Comments