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|$(数列中绝对值的最大值)