#6287. 诗歌

内存限制:512 MiB 时间限制:2000 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: BigFairyNBC

题目描述

小 F 是一个爱写诗的小姑娘。

“我能看一看你写的诗吗?”

“看吧,别念出来哦,我会害羞的。”

小 F 慵懒地坐在午后的阳光下,她在写诗,可是似乎没有什么灵感。

她用手指勾勒着远方绵延的山,就写关于远方的诗吧。

远方的山总共有 N 个山峰,从左往右第 i 个山峰有一个高度 H_i 。小 F 认为一个三元组 (i, j, k) 可以写成一首诗,当且仅当 1 \le i < j < k \le N H_i - H_j = H_j - H_k

小 F 和大 F 生活的国家—— Fairy 国地形十分奇特,保证 H_{1\ldots N} 一定是一个 1\ldots N 的排列。

小 F 想写诗给大 F 看,但是不知道自己能不能写成,于是她想问问你。

输入格式

第一行一个正整数 N ,表示山峰的数量。

第二行 N 个正整数 H_{1\ldots N} ,表示从左往右每座山峰的高度,保证是个 1\ldots N 的排列。

输出格式

一行一个字符串 YESNO ,表示小 F 能否写出一首诗,即是否存在三元组 (i, j, k) 满足 1 \le i < j < k \le N H_i - H_j = H_j - H_k

样例

样例输入 1

4
1 3 4 2

样例输出 1

NO

样例解释 1

不存在符合条件的三元组。

样例输入 2

5
1 5 2 4 3

样例输出 2

YES

样例解释 2

有两个符合条件的三元组。

第一个是 (1, 3, 5) ,此时 H_i=1, H_j=2, H_k=3

第二个是 (2, 4, 5) ,此时 H_i=5, H_j=4, H_k=3

所以此时符合条件的三元组存在,应当输出 YES

数据范围与提示

对于所有数据,保证 3 \le N \le 3\times 10^5

下表为各个 Subtask 的额外限制与得分,空格表示该项无额外限制。你只有通过一个 Subtask 的所有数据才能得到该 Subtask 的分。

Subtask 编号 N 分值
1 \le 300 19
2 \le 3000 22
3 59