/*
 * Kon Kon Fubuki
*/

#include <bits/stdc++.h>

using namespace std;

//basic types
using ll = long long;
using ld = long double;
using db = double;
using str = string;

using pi = pair<int,int>;
using pl = pair<ll,ll>;
using pd = pair<db,db>;

using vi = vector<int>;
using vb = vector<bool>;
using vl = vector<ll>;
using vd = vector<db>;
using vs = vector<str>;
using vpi = vector<pi>;
using vpl = vector<pl>;
using vpd = vector<pd>;

#define tcT template<class T
#define tcTU tcT, class U

tcT> using V = vector<T>; 
tcT, size_t SZ> using AR = array<T,SZ>; 
tcT> using PR = pair<T,T>;

// pairs
#define mp make_pair
#define f first
#define s second

// for vectors
#define sz(x) (int)(x).size()
#define all(x) begin(x), end(x)
#define rall(x) (x).rbegin(), (x).rend()
#define sor(x) sort(all(x))
#define rsz resize
#define ins insert
#define ft front()
#define bk back()
#define pf push_front
#define pb push_back
#define eb emplace_back
#define lb lower_bound
#define ub upper_bound

// loops
#define FOR(i,a,b) for (int i = (a); i < (b); i++)
#define F0R(i,a) FOR(i,0,a)
#define ROF(i,a,b) for (int i = (b)-1; i >= (a); i++)
#define R0F(i,a) ROF(i,0,a)
#define trav(a,x) for (auto& a: x)

const int MOD = 1e9+7;
const int mxN = 2e5+5;
const ll INF = 1e18;
const ld PI = acos((ld)-1);
const int tSZ = (1 << 21);
const int dx[4] = {1,0,-1,0}, dy[4] = {0,1,0,-1}; // for grid problems
mt19937 rng((uint32_t)chrono::steady_clock::now().time_since_epoch().count()); 

// useful functions
constexpr int pcnt(int x) { return __builtin_popcount(x); } // number of bits
constexpr int bits(int x) { return 31-__builtin_clz(x); } // log2(x) rounded down
ll cdiv(ll a, ll b) { return a/b+((a^b)>0&&a%b); } // divide a by b rounded up
ll fdiv(ll a, ll b) { return a/b-((a^b)<0&&a%b); } // divide a by b rounded down

// functions for working with MOD
ll add(ll f, ll s){ f += s; if(f >= MOD) f %= MOD; if(f < 0) f += MOD;	return f; } // add f to s and make sure it's in range
ll mul(ll f, ll s){ f *= s; if(f >= MOD) f %= MOD; return f;} // multiply f and s and make sure it's in range
ll pw(ll x, ll y) { ll ans = 1, ml = x; while(y) { if(y & 1) ans = mul(ans, ml); ml = mul(ml, ml);	y >>= 1; } return ans; } // number x to a power y
ll inv(ll x) { return pw(x, MOD - 2); } //inversion of a number

tcT> void remDup(vector<T>& x) { // sort and remove duplicates
	sort(all(x)); x.erase(unique(all(x)),end(x)); }
tcTU> void erase(T& x, const U& v) {
	auto it = x.find(v); assert(it != end(x));
	x.erase(v); }

// Input
#define tcTUU tcT, class ...U
tcT> void re(complex<T>& c);
tcTU> void re(pair<T,U>& p);
tcT> void re(vector<T>& v);
tcT, size_t SZ> void re(array<T,SZ>& a);

tcT> void re(T& x) { cin >> x; }
void re(db& d) { str t; re(t); d = stod(t); }
void re(ld& d) { str t; re(t); d = stold(t); }
tcTUU> void re(T& t, U&... u) { re(t); re(u...); }
 
tcT> void re(complex<T>& c) { T a,b; re(a,b); c = {a,b}; }
tcTU> void re(pair<T,U>& p) { re(p.f,p.s); }
tcT> void re(vector<T>& x) { trav(a,x) re(a); }
tcT, size_t SZ> void re(array<T,SZ>& x) { trav(a,x) re(a); }
tcT> void rv(int& n, vector<T>& x) { re(n); x.rsz(n); trav(a,x) re(a); }

// To_String
#define ts to_string
str ts(char c) { return str(1,c); }
str ts(const char* s) { return (str)s; }
str ts(str s) { return s; }
str ts(bool b) { 
	#ifdef LOCAL
		return b ? "true" : "false"; 
	#else 
		return ts((int)b);
	#endif
}
tcT> str ts(complex<T> c) { 
	stringstream ss; ss << c; return ss.str(); }
str ts(vector<bool> v) {
	str res = "{"; F0R(i,sz(v)) res += char('0'+v[i]);
	res += "}"; return res; }
template<size_t SZ> str ts(bitset<SZ> b) {
	str res = ""; F0R(i,SZ) res += char('0'+b[i]);
	return res; }
tcTU> str ts(pair<T,U> p);
tcT> str ts(T v) { // containers with begin(), end()
	#ifdef LOCAL
		bool fst = 1; str res = "{";
		for (const auto& x: v) {
			if (!fst) res += ", ";
			fst = 0; res += ts(x);
		}
		res += "}"; return res;
	#else
		bool fst = 1; str res = "";
		for (const auto& x: v) {
			if (!fst) res += " ";
			fst = 0; res += ts(x);
		}
		return res;
 
	#endif
}
tcTU> str ts(pair<T,U> p) {
	#ifdef LOCAL
		return "("+ts(p.f)+", "+ts(p.s)+")"; 
	#else
		return ts(p.f)+" "+ts(p.s);
	#endif
}
 
// Output
tcT> void pr(T v) { cout << ts(v); }
tcTUU> void pr(const T& t, const U&... u) { 
	pr(t); pr(u...); }
void ps() { pr("\n"); } // no spaces
tcTUU> void ps(const T& t, const U&... u) { 
	pr(t); if (sizeof...(u)) pr(" "); ps(u...); }
 
// File In/Out
void setIn(str s) { freopen(s.c_str(),"r", stdin); }
void setOut(str s) { freopen(s.c_str(),"w", stdout); }
void unsyncIO() { cin.tie(0)->sync_with_stdio(0); }
void setIO(str st = "") {
	unsyncIO();
	if (sz(st)) { setIn(st+".in"), setOut(st+".out"); } // If problem requires file reading
}

int n, a[mxN], br[2][mxN], br2[2][mxN];

void pre_c(int st, int ed, int ty)
{
	int ps = 1; if(ty == 1) ps = -1;
	int cnt = 1, cnt2 = 1;
	br[ty][st] = 1;
	br2[ty][st] = 1;
	for(int i = st + ps; i != ed; i += ps)
	{
		if(a[i] < a[i - ps]) cnt2++;
		else cnt2 = 1;
		if(a[i] > a[i - ps]) cnt++;
		else
		{
			cnt = 1;
		}
		br2[ty][i] = cnt2;
		br[ty][i] = cnt;
	}
}

int calc(int f, int s, int t, int h)
{
	//if(f == s) return 0;
	if(f > s)
	{
		swap(f, s);
		swap(t, h);
	}
	//ps(f, s, t, h);
	if(s == max(t, h)) return 0;
	for(int i = s; i >= f; i--)
	{
		if(i % 2 == 0) return 0;
	}
	return 1;
}

int solve()
{
	pre_c(0, n, 0);
	pre_c(n - 1, -1, 1);
	int mx = 0;
	FOR(i, 0, n) mx = max(mx, max(br[0][i], br[1][i]));
	int ans = 0;
	int tt = 0;
	FOR(i, 0, n)
	{
		if(max(br[0][i], br[1][i]) == mx) 
		{
			tt++;
			//ps(i, br[0][i], br[1][i]);
			ans += calc(br[0][i], br[1][i], br2[0][i - br[0][i] + 1], br2[1][i - 1 + br[1][i]]);
		}
	}
	if(tt >= 2) ans = 0;
	return ans;
}

int main()
{
	setIO();

	re(n);
	FOR(i, 0, n)
	{
		re(a[i]);
	}
	ps(solve());

	return 0;
	//read stuff at the bottom ffs
}
/* things to keep in mind 
 * int overflow, array bounds
 * any special cases
 * always do something
 * WRITE STUFF DOWN
 * THINK ABOUT OTHER APPROACHES
 * DON'T NON STOP CHECK OTHERS
 * DON'T PANIC
*/


### Prompt

Please provide a Cpp coded solution 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
/*
 * Kon Kon Fubuki
*/

#include <bits/stdc++.h>

using namespace std;

//basic types
using ll = long long;
using ld = long double;
using db = double;
using str = string;

using pi = pair<int,int>;
using pl = pair<ll,ll>;
using pd = pair<db,db>;

using vi = vector<int>;
using vb = vector<bool>;
using vl = vector<ll>;
using vd = vector<db>;
using vs = vector<str>;
using vpi = vector<pi>;
using vpl = vector<pl>;
using vpd = vector<pd>;

#define tcT template<class T
#define tcTU tcT, class U

tcT> using V = vector<T>; 
tcT, size_t SZ> using AR = array<T,SZ>; 
tcT> using PR = pair<T,T>;

// pairs
#define mp make_pair
#define f first
#define s second

// for vectors
#define sz(x) (int)(x).size()
#define all(x) begin(x), end(x)
#define rall(x) (x).rbegin(), (x).rend()
#define sor(x) sort(all(x))
#define rsz resize
#define ins insert
#define ft front()
#define bk back()
#define pf push_front
#define pb push_back
#define eb emplace_back
#define lb lower_bound
#define ub upper_bound

// loops
#define FOR(i,a,b) for (int i = (a); i < (b); i++)
#define F0R(i,a) FOR(i,0,a)
#define ROF(i,a,b) for (int i = (b)-1; i >= (a); i++)
#define R0F(i,a) ROF(i,0,a)
#define trav(a,x) for (auto& a: x)

const int MOD = 1e9+7;
const int mxN = 2e5+5;
const ll INF = 1e18;
const ld PI = acos((ld)-1);
const int tSZ = (1 << 21);
const int dx[4] = {1,0,-1,0}, dy[4] = {0,1,0,-1}; // for grid problems
mt19937 rng((uint32_t)chrono::steady_clock::now().time_since_epoch().count()); 

// useful functions
constexpr int pcnt(int x) { return __builtin_popcount(x); } // number of bits
constexpr int bits(int x) { return 31-__builtin_clz(x); } // log2(x) rounded down
ll cdiv(ll a, ll b) { return a/b+((a^b)>0&&a%b); } // divide a by b rounded up
ll fdiv(ll a, ll b) { return a/b-((a^b)<0&&a%b); } // divide a by b rounded down

// functions for working with MOD
ll add(ll f, ll s){ f += s; if(f >= MOD) f %= MOD; if(f < 0) f += MOD;	return f; } // add f to s and make sure it's in range
ll mul(ll f, ll s){ f *= s; if(f >= MOD) f %= MOD; return f;} // multiply f and s and make sure it's in range
ll pw(ll x, ll y) { ll ans = 1, ml = x; while(y) { if(y & 1) ans = mul(ans, ml); ml = mul(ml, ml);	y >>= 1; } return ans; } // number x to a power y
ll inv(ll x) { return pw(x, MOD - 2); } //inversion of a number

tcT> void remDup(vector<T>& x) { // sort and remove duplicates
	sort(all(x)); x.erase(unique(all(x)),end(x)); }
tcTU> void erase(T& x, const U& v) {
	auto it = x.find(v); assert(it != end(x));
	x.erase(v); }

// Input
#define tcTUU tcT, class ...U
tcT> void re(complex<T>& c);
tcTU> void re(pair<T,U>& p);
tcT> void re(vector<T>& v);
tcT, size_t SZ> void re(array<T,SZ>& a);

tcT> void re(T& x) { cin >> x; }
void re(db& d) { str t; re(t); d = stod(t); }
void re(ld& d) { str t; re(t); d = stold(t); }
tcTUU> void re(T& t, U&... u) { re(t); re(u...); }
 
tcT> void re(complex<T>& c) { T a,b; re(a,b); c = {a,b}; }
tcTU> void re(pair<T,U>& p) { re(p.f,p.s); }
tcT> void re(vector<T>& x) { trav(a,x) re(a); }
tcT, size_t SZ> void re(array<T,SZ>& x) { trav(a,x) re(a); }
tcT> void rv(int& n, vector<T>& x) { re(n); x.rsz(n); trav(a,x) re(a); }

// To_String
#define ts to_string
str ts(char c) { return str(1,c); }
str ts(const char* s) { return (str)s; }
str ts(str s) { return s; }
str ts(bool b) { 
	#ifdef LOCAL
		return b ? "true" : "false"; 
	#else 
		return ts((int)b);
	#endif
}
tcT> str ts(complex<T> c) { 
	stringstream ss; ss << c; return ss.str(); }
str ts(vector<bool> v) {
	str res = "{"; F0R(i,sz(v)) res += char('0'+v[i]);
	res += "}"; return res; }
template<size_t SZ> str ts(bitset<SZ> b) {
	str res = ""; F0R(i,SZ) res += char('0'+b[i]);
	return res; }
tcTU> str ts(pair<T,U> p);
tcT> str ts(T v) { // containers with begin(), end()
	#ifdef LOCAL
		bool fst = 1; str res = "{";
		for (const auto& x: v) {
			if (!fst) res += ", ";
			fst = 0; res += ts(x);
		}
		res += "}"; return res;
	#else
		bool fst = 1; str res = "";
		for (const auto& x: v) {
			if (!fst) res += " ";
			fst = 0; res += ts(x);
		}
		return res;
 
	#endif
}
tcTU> str ts(pair<T,U> p) {
	#ifdef LOCAL
		return "("+ts(p.f)+", "+ts(p.s)+")"; 
	#else
		return ts(p.f)+" "+ts(p.s);
	#endif
}
 
// Output
tcT> void pr(T v) { cout << ts(v); }
tcTUU> void pr(const T& t, const U&... u) { 
	pr(t); pr(u...); }
void ps() { pr("\n"); } // no spaces
tcTUU> void ps(const T& t, const U&... u) { 
	pr(t); if (sizeof...(u)) pr(" "); ps(u...); }
 
// File In/Out
void setIn(str s) { freopen(s.c_str(),"r", stdin); }
void setOut(str s) { freopen(s.c_str(),"w", stdout); }
void unsyncIO() { cin.tie(0)->sync_with_stdio(0); }
void setIO(str st = "") {
	unsyncIO();
	if (sz(st)) { setIn(st+".in"), setOut(st+".out"); } // If problem requires file reading
}

int n, a[mxN], br[2][mxN], br2[2][mxN];

void pre_c(int st, int ed, int ty)
{
	int ps = 1; if(ty == 1) ps = -1;
	int cnt = 1, cnt2 = 1;
	br[ty][st] = 1;
	br2[ty][st] = 1;
	for(int i = st + ps; i != ed; i += ps)
	{
		if(a[i] < a[i - ps]) cnt2++;
		else cnt2 = 1;
		if(a[i] > a[i - ps]) cnt++;
		else
		{
			cnt = 1;
		}
		br2[ty][i] = cnt2;
		br[ty][i] = cnt;
	}
}

int calc(int f, int s, int t, int h)
{
	//if(f == s) return 0;
	if(f > s)
	{
		swap(f, s);
		swap(t, h);
	}
	//ps(f, s, t, h);
	if(s == max(t, h)) return 0;
	for(int i = s; i >= f; i--)
	{
		if(i % 2 == 0) return 0;
	}
	return 1;
}

int solve()
{
	pre_c(0, n, 0);
	pre_c(n - 1, -1, 1);
	int mx = 0;
	FOR(i, 0, n) mx = max(mx, max(br[0][i], br[1][i]));
	int ans = 0;
	int tt = 0;
	FOR(i, 0, n)
	{
		if(max(br[0][i], br[1][i]) == mx) 
		{
			tt++;
			//ps(i, br[0][i], br[1][i]);
			ans += calc(br[0][i], br[1][i], br2[0][i - br[0][i] + 1], br2[1][i - 1 + br[1][i]]);
		}
	}
	if(tt >= 2) ans = 0;
	return ans;
}

int main()
{
	setIO();

	re(n);
	FOR(i, 0, n)
	{
		re(a[i]);
	}
	ps(solve());

	return 0;
	//read stuff at the bottom ffs
}
/* things to keep in mind 
 * int overflow, array bounds
 * any special cases
 * always do something
 * WRITE STUFF DOWN
 * THINK ABOUT OTHER APPROACHES
 * DON'T NON STOP CHECK OTHERS
 * DON'T PANIC
*/


```