#35 「 插入排序 」

统计

R君有一个数字序列$a_1,a_2,\ldots,a_n$,长度为n,R君只有一个操作:选定p($1 \le p\le n$),然后把$a_p$从序列里拿出,然后再插入到序列中任意位置。

比如a序列为1,2,4,5,3,$p=5$,可以取出3,然后在任意位置插入,可以变为1,2,3,4,5。

现在给你一个序列a,问你是否可以通过一次操作把整个序列从小到大排好序(变成不降的)。

输入格式

第一行一个整数n,第二行空格隔开的n个整数,代表a序列。

输出格式

如果可以一次操作可以排好序,输出"YES",否则输出"NO"。

样例数据

input

5
1 2 4 5 3

output

YES

数据规模与约定

$n \le 10^6, 1 \le a_i \le 10^6 $。

时间限制:1s

空间限制:512MB

Author: zrt