Description

Xiaoqiang really likes sequences. One day, on a whim, he wrote down a sequence.

Amiba also likes sequences, but he only likes one kind: wave sequences.

A wave sequence of length $n$ satisfies, for any $i\ (1 \le i < n)$, exactly one of the following two sets of conditions (the same one):

• $a_{2i-1} \le a_{2i}$ and $a_{2i} \ge a_{2i+1}$ (if it exists).
• $a_{2i-1} \ge a_{2i}$ and $a_{2i} \le a_{2i+1}$ (if it exists).

Amiba told Xiaoqiang about his preference. Xiaoqiang decided to make a small change to turn the sequence into a wave sequence. He wants to know whether it is possible to make the original sequence a wave sequence by modifying at most one number (or not modifying it).

Input Format

The input contains multiple test cases.

Each test case consists of two lines:

• The first line contains an integer $n$ denoting the length of the sequence.
• The second line contains $n$ integers, representing a sequence.

Output Format

For each test case, output one line Yes or No, as described.

5
1 2 3 2 1
5
1 2 3 4 5

Yes
No

Hint

Constraints and Conventions

• For $30\%$ of the testdata, $1 \le n \le 10$.
• For another $30\%$ of the testdata, $1 \le m \le 1000$.
• For $100\%$ of the testdata, $1 \le n \le 10^5$, $m \le 10^9$.

Here $m = \max|a_i|$ (the maximum absolute value in the sequence).

Translated by ChatGPT 5