#include<bits/stdc++.h>
#include<iostream>
#include<string>
#include<cmath>
#include<cstdio>
#include<cctype>
#include<cstring>
#include<iomanip>
#include<cstdlib>
#include<ctime>
#include<set>
#include<map>
#include<utility>
#include<queue>
#include<vector>
#include<stack>
#include<sstream>
#include<algorithm>
#define forn(i,a,b)for(int i=(a),_b=(b);i<=_b;i++)
#define fore(i,b,a)for(int i=(b),_a=(a);i>=_a;i--)
#define rep(i,n)for(int i=0,_n=n;i<n;i++)
#define ll long long
#define pii pair<int,int>
#define vi vector<int>
#define vpii vector<pii>
#define p_q priority_queue
#define m_p make_pair
#define pb push_back
#define ld long double
#define F first
#define S second
#define ull unsigned long long
#define mod 1000000007
#define md 998244353
#define x1 XZVJDFADSPFOE
#define y1 GASDIJSLDAEJF
#define x2 DFDAJKVOHKWIW
#define y2 PSFSAODSXVNMQ
#define LLINF 0x3f3f3f3f3f3f3f3fLL
#define foreach(i,c) for(__typeof(c.begin())i=(c.begin());i!=(c).end();i++)
using namespace std;
inline void read(int &x)
{
	short negative=1;
    x=0;
    char c=getchar();
    while(c<'0' || c>'9')
    {
		if(c=='-')
			negative=-1;
		c=getchar();
	}
    while(c>='0' && c<='9')
        x=(x<<3)+(x<<1)+(c^48),c=getchar();
    x*=negative;
}
ll qpow(ll n,ll k){
	ll ans=1;
	while(k){
		if(k%2){
			ans*=n;
			ans%=mod;
		}
		n*=n;
		n%=mod;
		k/=2;
	}
	return ans;
}
string iots(int n)
{
	string s="";
	while(n)
	{
		int now=n%10;
		s+=now+'0';
		n/=10;
	}
	reverse(s.begin(),s.end());
	return s;
}
int stoi(string s)
{
	int n=0;
	rep(i,s.size())
	{
		n*=10;
		n+=s[i]-'0';
	}
	return n;
}
int n;
int p[100100];
int pr[100100];
int suf[100100];
//pr[i]->i山峰左边能到的最远的地方 suf[i]右边 
int main()
{
	ios::sync_with_stdio(0);
	cin>>n;
	rep(i,n)cin>>p[i]; 
	pr[0]=0;
	forn(i,1,n-1)
	{
		if(p[i]>p[i-1])
		{
			pr[i]=pr[i-1]; 
		} 
		else 
		{
			pr[i]=i;
		}
	}
	suf[n-1]=n-1;
	fore(i,n-2,0)
	{
		if(p[i]>p[i+1])
		{
			suf[i]=suf[i+1];
		}
		else
		{
			suf[i]=i;
		}
	}
	int mx=0;
	rep(i,n)
	{
		if(pr[i]==i||suf[i]==i)continue;
		if(i-pr[i]==suf[i]-i)
		{
			mx=max(mx,i-pr[i]);
		}
	}
	int ans=0;
	rep(i,n)
	{
		if(pr[i]==i||suf[i]==i)continue;
		if(i-pr[i]==suf[i]-i&&i-pr[i]==mx)
		{
			ans++;
		}
	}
	int cnt=0;
	rep(i,n)
	{
		if(i-pr[i]==mx)cnt++;
		if(suf[i]-i==mx)cnt++;
	 } 
	if(mx==0||mx%2==1||cnt>=3)
	{
		cout<<0<<endl;
		return 0;
	}
	if(ans==1) cout<<1<<endl;
	else cout<<0<<endl;
	return 0;
}
//特判判全
//循环边界
//精度足够
//注意初值

### Prompt

Develop a solution in cpp to the problem described below:

On a weekend, Qingshan suggests that she and her friend Daniel go hiking. Unfortunately, they are busy high school students, so they can only go hiking on scratch paper.

A permutation p is written from left to right on the paper. First Qingshan chooses an integer index x (1≤ x≤ n) and tells it to Daniel. After that, Daniel chooses another integer index y (1≤ y≤ n, y ≠ x).

The game progresses turn by turn and as usual, Qingshan moves first. The rules follow: 

  * If it is Qingshan's turn, Qingshan must change x to such an index x' that 1≤ x'≤ n, |x'-x|=1, x'≠ y, and p_{x'}<p_x at the same time. 
  * If it is Daniel's turn, Daniel must change y to such an index y' that 1≤ y'≤ n, |y'-y|=1, y'≠ x, and p_{y'}>p_y at the same time. 



The person who can't make her or his move loses, and the other wins. You, as Qingshan's fan, are asked to calculate the number of possible x to make Qingshan win in the case both players play optimally.

Input

The first line contains a single integer n (2≤ n≤ 10^5) — the length of the permutation.

The second line contains n distinct integers p_1,p_2,...,p_n (1≤ p_i≤ n) — the permutation.

Output

Print the number of possible values of x that Qingshan can choose to make her win.

Examples

Input


5
1 2 5 4 3


Output


1


Input


7
1 2 4 6 5 3 7


Output


0

Note

In the first test case, Qingshan can only choose x=3 to win, so the answer is 1.

In the second test case, if Qingshan will choose x=4, Daniel can choose y=1. In the first turn (Qingshan's) Qingshan chooses x'=3 and changes x to 3. In the second turn (Daniel's) Daniel chooses y'=2 and changes y to 2. Qingshan can't choose x'=2 because y=2 at this time. Then Qingshan loses.

### Response

```cpp
#include<bits/stdc++.h>
#include<iostream>
#include<string>
#include<cmath>
#include<cstdio>
#include<cctype>
#include<cstring>
#include<iomanip>
#include<cstdlib>
#include<ctime>
#include<set>
#include<map>
#include<utility>
#include<queue>
#include<vector>
#include<stack>
#include<sstream>
#include<algorithm>
#define forn(i,a,b)for(int i=(a),_b=(b);i<=_b;i++)
#define fore(i,b,a)for(int i=(b),_a=(a);i>=_a;i--)
#define rep(i,n)for(int i=0,_n=n;i<n;i++)
#define ll long long
#define pii pair<int,int>
#define vi vector<int>
#define vpii vector<pii>
#define p_q priority_queue
#define m_p make_pair
#define pb push_back
#define ld long double
#define F first
#define S second
#define ull unsigned long long
#define mod 1000000007
#define md 998244353
#define x1 XZVJDFADSPFOE
#define y1 GASDIJSLDAEJF
#define x2 DFDAJKVOHKWIW
#define y2 PSFSAODSXVNMQ
#define LLINF 0x3f3f3f3f3f3f3f3fLL
#define foreach(i,c) for(__typeof(c.begin())i=(c.begin());i!=(c).end();i++)
using namespace std;
inline void read(int &x)
{
	short negative=1;
    x=0;
    char c=getchar();
    while(c<'0' || c>'9')
    {
		if(c=='-')
			negative=-1;
		c=getchar();
	}
    while(c>='0' && c<='9')
        x=(x<<3)+(x<<1)+(c^48),c=getchar();
    x*=negative;
}
ll qpow(ll n,ll k){
	ll ans=1;
	while(k){
		if(k%2){
			ans*=n;
			ans%=mod;
		}
		n*=n;
		n%=mod;
		k/=2;
	}
	return ans;
}
string iots(int n)
{
	string s="";
	while(n)
	{
		int now=n%10;
		s+=now+'0';
		n/=10;
	}
	reverse(s.begin(),s.end());
	return s;
}
int stoi(string s)
{
	int n=0;
	rep(i,s.size())
	{
		n*=10;
		n+=s[i]-'0';
	}
	return n;
}
int n;
int p[100100];
int pr[100100];
int suf[100100];
//pr[i]->i山峰左边能到的最远的地方 suf[i]右边 
int main()
{
	ios::sync_with_stdio(0);
	cin>>n;
	rep(i,n)cin>>p[i]; 
	pr[0]=0;
	forn(i,1,n-1)
	{
		if(p[i]>p[i-1])
		{
			pr[i]=pr[i-1]; 
		} 
		else 
		{
			pr[i]=i;
		}
	}
	suf[n-1]=n-1;
	fore(i,n-2,0)
	{
		if(p[i]>p[i+1])
		{
			suf[i]=suf[i+1];
		}
		else
		{
			suf[i]=i;
		}
	}
	int mx=0;
	rep(i,n)
	{
		if(pr[i]==i||suf[i]==i)continue;
		if(i-pr[i]==suf[i]-i)
		{
			mx=max(mx,i-pr[i]);
		}
	}
	int ans=0;
	rep(i,n)
	{
		if(pr[i]==i||suf[i]==i)continue;
		if(i-pr[i]==suf[i]-i&&i-pr[i]==mx)
		{
			ans++;
		}
	}
	int cnt=0;
	rep(i,n)
	{
		if(i-pr[i]==mx)cnt++;
		if(suf[i]-i==mx)cnt++;
	 } 
	if(mx==0||mx%2==1||cnt>=3)
	{
		cout<<0<<endl;
		return 0;
	}
	if(ans==1) cout<<1<<endl;
	else cout<<0<<endl;
	return 0;
}
//特判判全
//循环边界
//精度足够
//注意初值

```