#include <bits/stdc++.h>

using namespace std;

typedef unsigned uint;
typedef long long ll;
typedef unsigned long long ull;
typedef long double ldbl;
typedef pair<int, int> pii;
typedef pair<uint, uint> puu;
typedef pair<ll, ll> pll;
typedef pair<ull, ull> pull;
typedef pair<double, double> pdd;
typedef vector<int> vi;
typedef vector<uint> vu;
typedef vector<ll> vll;
typedef vector<ull> vull;
typedef vector<pii> vpii;
typedef vector<puu> vpuu;
typedef vector<pll> vpll;
typedef vector<pull> vpull;
typedef vector<string> vstr;
typedef vector<double> vdbl;
typedef vector<ldbl> vldbl;
#define pb push_back
#define ppb pop_back
#define pfr push_front
#define ppfr pop_front
#define emp emplace
#define empb emplace_back
#define be begin
#define rbe rbegin
#define all(x) (x).be(), (x).end()
#define rall(x) (x).rbe(), (x).rend()
#define fir first
#define sec second
#define mkp make_pair
#define brif(cond) if (cond) break
#define ctif(cond) if (cond) continue
#define retif(cond) if (cond) return
void canhazfast() {ios_base::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);}
template<typename T> T gcd(T a, T b) {return b ? gcd(b, a%b) : a;}
template<typename T> T extgcd(T a, T b, T &x, T &y)
{
    T x0 = 1, y0 = 0, x1 = 0, y1 = 1;
    while (b) {
        T q = a/b; a %= b; swap(a, b);
        x0 -= q*x1; swap(x0, x1);
        y0 -= q*y1; swap(y0, y1);
    }
    x = x0; y = y0; return a;
}
int ctz(uint x) {return __builtin_ctz(x);}
int ctzll(ull x) {return __builtin_ctzll(x);}
int clz(uint x) {return __builtin_clz(x);}
int clzll(ull x) {return __builtin_clzll(x);}
int popcnt(uint x) {return __builtin_popcount(x);}
int popcntll(ull x) {return __builtin_popcountll(x);}
int bsr(uint x) {return 31^clz(x);}
int bsrll(ull x) {return 63^clzll(x);}

#define N 100016

int sgn(int x)
{
    return x < 0 ? -1 : x > 0;
}

int p[N], d[N];

int main()
{
    canhazfast();

    int n, k = 0;
    int dmx = 0, cnt = 0;
    int ans = 0;

    cin >> n;
    for (int i = 1; i <= n; ++i) cin >> p[i];
    for (int i = 1; i < n; ) {
        int dir = sgn(p[i+1]-p[i]);
        int len = dir;
        int j = i+1;
        while (j < n && sgn(p[j+1]-p[j]) == dir) {
            ++j;
            len += dir;
        }
        d[k++] = len;
        i = j;
    }
    //cerr << "d =";
    for (int i = 0; i < k; ++i) {
        //cerr << ' ' << d[i];
        int len = abs(d[i]);
        if (dmx < len) {
            dmx = len;
            cnt = 0;
        }
        if (dmx == len) ++cnt;
    }
    //cerr << '\n';
    for (int i = 1; i < k; ++i) {
        ctif(d[i] > 0);
        int lo, hi;
        tie(lo, hi) = minmax(d[i-1], -d[i]);
        if (lo == hi && hi == dmx && cnt <= 2 && hi%2 == 0) ++ans;
    }
    cout << ans << '\n';

    return 0;
}

### Prompt

Create a solution in Cpp for the following problem:

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>

using namespace std;

typedef unsigned uint;
typedef long long ll;
typedef unsigned long long ull;
typedef long double ldbl;
typedef pair<int, int> pii;
typedef pair<uint, uint> puu;
typedef pair<ll, ll> pll;
typedef pair<ull, ull> pull;
typedef pair<double, double> pdd;
typedef vector<int> vi;
typedef vector<uint> vu;
typedef vector<ll> vll;
typedef vector<ull> vull;
typedef vector<pii> vpii;
typedef vector<puu> vpuu;
typedef vector<pll> vpll;
typedef vector<pull> vpull;
typedef vector<string> vstr;
typedef vector<double> vdbl;
typedef vector<ldbl> vldbl;
#define pb push_back
#define ppb pop_back
#define pfr push_front
#define ppfr pop_front
#define emp emplace
#define empb emplace_back
#define be begin
#define rbe rbegin
#define all(x) (x).be(), (x).end()
#define rall(x) (x).rbe(), (x).rend()
#define fir first
#define sec second
#define mkp make_pair
#define brif(cond) if (cond) break
#define ctif(cond) if (cond) continue
#define retif(cond) if (cond) return
void canhazfast() {ios_base::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);}
template<typename T> T gcd(T a, T b) {return b ? gcd(b, a%b) : a;}
template<typename T> T extgcd(T a, T b, T &x, T &y)
{
    T x0 = 1, y0 = 0, x1 = 0, y1 = 1;
    while (b) {
        T q = a/b; a %= b; swap(a, b);
        x0 -= q*x1; swap(x0, x1);
        y0 -= q*y1; swap(y0, y1);
    }
    x = x0; y = y0; return a;
}
int ctz(uint x) {return __builtin_ctz(x);}
int ctzll(ull x) {return __builtin_ctzll(x);}
int clz(uint x) {return __builtin_clz(x);}
int clzll(ull x) {return __builtin_clzll(x);}
int popcnt(uint x) {return __builtin_popcount(x);}
int popcntll(ull x) {return __builtin_popcountll(x);}
int bsr(uint x) {return 31^clz(x);}
int bsrll(ull x) {return 63^clzll(x);}

#define N 100016

int sgn(int x)
{
    return x < 0 ? -1 : x > 0;
}

int p[N], d[N];

int main()
{
    canhazfast();

    int n, k = 0;
    int dmx = 0, cnt = 0;
    int ans = 0;

    cin >> n;
    for (int i = 1; i <= n; ++i) cin >> p[i];
    for (int i = 1; i < n; ) {
        int dir = sgn(p[i+1]-p[i]);
        int len = dir;
        int j = i+1;
        while (j < n && sgn(p[j+1]-p[j]) == dir) {
            ++j;
            len += dir;
        }
        d[k++] = len;
        i = j;
    }
    //cerr << "d =";
    for (int i = 0; i < k; ++i) {
        //cerr << ' ' << d[i];
        int len = abs(d[i]);
        if (dmx < len) {
            dmx = len;
            cnt = 0;
        }
        if (dmx == len) ++cnt;
    }
    //cerr << '\n';
    for (int i = 1; i < k; ++i) {
        ctif(d[i] > 0);
        int lo, hi;
        tie(lo, hi) = minmax(d[i-1], -d[i]);
        if (lo == hi && hi == dmx && cnt <= 2 && hi%2 == 0) ++ans;
    }
    cout << ans << '\n';

    return 0;
}

```