P3929 SAC E#1 - A Legendary Problem Sequence1

Xiaoqiang and Amiba are good friends.

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).

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.

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

### 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