B. Pillars

There are nn pillars aligned in a row and numbered from 11 to nn.

Initially each pillar contains exactly one disk. The ii-th pillar contains a disk having radius aiai.

You can move these disks from one pillar to another. You can take a disk from pillar ii and place it on top of pillar jj if all these conditions are met:

1. there is no other pillar between pillars ii and jj. Formally, it means that |i−j|=1|i−j|=1;
2. pillar ii contains exactly one disk;
3. either pillar jj contains no disks, or the topmost disk on pillar jj has radius strictly greater than the radius of the disk you move.

When you place a disk on a pillar that already has some disks on it, you put the new disk on top of previously placed disks, so the new disk will be used to check the third condition if you try to place another disk on the same pillar.

You may take any disk and place it on other pillar any number of times, provided that every time you do it, all three aforementioned conditions are met. Now you wonder, is it possible to place all nn disks on the same pillar simultaneously?

Input

The first line contains one integer nn (3≤n≤2⋅1053≤n≤2⋅105) — the number of pillars.

The second line contains nn integers a1a1, a2a2, ..., aiai (1≤ai≤n1≤ai≤n), where aiai is the radius of the disk initially placed on the ii-th pillar. All numbers aiai are distinct.

Output

Print YES if it is possible to place all the disks on the same pillar simultaneously, and NO otherwise. You may print each letter in any case (YES, yes, Yes will all be recognized as positive answer, NO, no and nO will all be recognized as negative answer).

Examples

input

4
1 3 4 2

output

YES

input

3
3 1 2

output

NO

题意：类似于汉诺塔，加了个限制：只能从相邻的两个柱子上转移盘子，小的盘子可以放在大的盘子上，问最终能否将所有盘子按照顺序放在同一根柱子上

因为最终要转移到一个柱子上，所以从最大的盘子开始，将相邻的盘子从大到小依次放到这根柱子上

从中间向两遍进行遍历，最终两端的盘子都能转移则代表成功

如果已经放上的盘子比下一个盘子小，则证明转移不能成功

代码：

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define inf 0x3f3f3f3f
#define mem(a,b) memset(a,b,sizeof(a))

int a[200005];

int main()
{
	int n,i,maxn=-inf,k=0,flag=1;
	cin>>n;
	for(i=1;i<=n;i++)
	{
		cin>>a[i];
		if(maxn<a[i])
		{
			maxn=a[i];
			k=i;
		}
	}
	a[0]=0;
	a[n+1]=0;
	int l=k-1,r=k+1;
	while(1)
	{
		if(l<=0&&r>=n+1)
			break;
		if(a[l]>a[k]||a[r]>a[k])    //如果盘子比已经放上去的盘子大，则转移不成功
		{
			flag=0;
			break;
		}
		if(a[l]>a[r])                //优先放上大的盘子
		{
			k=l;
			l--;
		}
		else
		{
			k=r;
			r++;
		}
	}
	if(flag&&l==0&&r==n+1)
		cout<<"YES"<<endl;
	else
		cout<<"NO"<<endl;
	return 0;
}