SAC E#1 - 一道神题 Sequence1

题目背景

小强和阿米巴是好朋友。

题目描述

小强很喜欢数列。有一天,他心血来潮,写下了一个数列。 阿米巴也很喜欢数列。但是他只喜欢其中一种:波动数列。 一个长度为 $n$ 的波动数列满足对于任何 $i\ (1 \le i < n)$,均满足以下两个条件至少一个: - $a_{2i-1} \le a_{2i}$ 且 $a_{2i} \ge a_{2i+1}$(若存在)。 - $a_{2i-1} \ge a_{2i}$ 且 $a_{2i} \le a_{2i+1}$(若存在)。 阿米巴把他的喜好告诉了小强。小强便打算稍作修改,以让这个数列成为波动数列。他想知道,能否通过仅修改一个数(或不修改),使得原数列变成波动数列。

输入输出格式

输入格式


输入包含多组数据。 每组数据包含两行: - 第一行一个整数 $n$ 表示数列的长度。 - 接下来一行,$n$ 个整数,表示一个数列。

输出格式


对于每一组输入,输出一行 `Yes` 或 `No`,含义如题目所示。

输入输出样例

输入样例 #1

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

输出样例 #1

Yes
No

说明

### 数据范围及约定 - 对于 $30\%$ 的数据,$1\le n \le 10$。 - 对于另外 $30\%$ 的数据,$1\le m \le 1000$。 - 对于 $100\%$ 的数据,$1\le n \le 10^5$,$m \le 10^9$。 其中 $m = \max|a_i|$(数列中绝对值的最大值)