2052 - 队列的序列

通过次数

7

提交次数

18

时间限制 : 1 秒
内存限制 : 128 MB

现在告诉你有一个队列,一开始它是空的,首先你会把 1,2,3,…m 这 m 个数依次push入这个队列。

接着,会进行 n 次操作,每次操作你需要进行如下操作:

首先,获得队首元素,输出队首元素,并且将这个队首元素pop出队列;然后你可以在如下两个选择中任选一个操作:

1. 将这个队首元素永远的抛弃;

2. 将这个队首元素重新加入到队尾中。

现在告诉你 n 和 n 次操作所输出的队首元素,需要你判断是否存在一个数 m 使得这个操作是可行的。

输入

第一行一个正整数 n ,用于表示操作的次数。(1≤n≤100000)

第二行 n 个正整数,以空格分隔,用于表示 n 次操作所输出的队首元素。

输出

如果存在一个数 m 使得这 n 次操作可行,输出“YES”;否则,输出“NO”。

样例

输入

5
1 2 3 1 2

输出

YES

输入

5
1 2 3 2 1

输出

NO

提示

【样例解释】

对于样例 1,当 m==3 时,我们执行如下操作就可以得到目标序列 [1,2,3,2,1]

初始时,que = [1,2,3]

step.1: 输出 1 = que.front(), que.pop(), que.push(1), 此时 que = [2,3,1]

step.2: 输出 2 = que.front(), que.pop(), que.push(2),此时 que = [3,1,2]

step.3: 输出 3 = que.front(), que.pop(), que.push(3), 此时 que = [1,2,3]

step.4: 输出 1 = que.front(), que.pop(), 此时 que = [2,3]

step.5: 输出 2 = que.fornt(), que.pop(), 此时 que = [3]

那么我们输出的序列就是 [1,2,3,1,2],所以 m==3 是存在的。这个序列合法,我们输出“YES”。

对于样例 2,我们没有办法得到m。

因为我们在 1, 2, 3 之后输出了 2,也就是说我一开始抛弃了 1 ,并且 m==3,那么到此我输出 2 是合法的,

但是我在2 之后又输出了 1,但是模拟到这里我们可以明显看出 1 肯定是在之前被抛弃了。所以你个序列不合法,输出“NO”。

【数据规模】

50% 的数据,满足 1≤n≤1000;

100%的数据,满足 1≤n≤100000。