///
/// Header; mostly generic
///
#include <cassert>
#include <ctime>
#include <iostream>
#include <cstdio>
#include <vector>
#include <algorithm>
#include <string>


const bool numTestsGiven = false;
const bool debug = true;

using namespace std;
typedef long long ll;

#define err(...) if (debug) fprintf(stderr,__VA_ARGS__)
#define debug(exp) if (debug) cerr << #exp << " = " << (exp) << " "
#define myscanf(exp, num, ...) if (scanf(exp,__VA_ARGS__) != num) return false;

///
/// Testcase variables
///
int n;
const int maxn = 100000;
int p[maxn+1];

vector<pair<int,int> > peaks; // stores lengths of slopes on both sides, larger one first
///
/// Solution
///

void offer(int incs, int decs) {
    if (incs < decs) swap(incs,decs);
    peaks.push_back(pair<int,int>(incs, decs));
}

bool peakCmp(pair<int,int> &a, pair<int,int> &b) {
    if (a.first > b.first) return true;
    if (a.first < b.first) return false;
    return (a.second > b.second);
}

void solve_testcase() {
    peaks.clear();
    // Iterate through all local maxima, and log the lengths of the "slopes" on both sides
    int incs = 0;
    int decs = 0;
    for (int i=2; i<=n; i++) {
        if (p[i] > p[i-1]) {
            if (decs == 0) { // continue an existing up-slope
                incs++;
            } else { // start a new up-slope
                offer(incs,decs);
                decs = 0;
                incs = 1;
            }
        } else { 
            decs++;
        }
    }
    offer(incs,decs);
    sort(peaks.begin(), peaks.end(), peakCmp);

    // Qinghsan wins iff the longest slope has even lenght, is tied with the slope on the otehr side of that peak, and is longer than all other slopes. He has only one winning move in that case.
    if (peaks[0].first % 2 == 0 && peaks[0].first == peaks[0].second) {
        if (peaks.size() == 1 || peaks[0].first > peaks[1].first) printf("1\n");
        else printf("0\n");
    } else {
        printf("0\n");
    }
}

bool read_testcase() {
    cin >> n;
    for (int i=1; i<=n; i++) scanf("%d",p+i);
    return cin.good();
}

///
/// Generic I/O code (not problem-specific)
///

int main(int argc, char **argv) {
    if (argc>1 && argv[1][0]!= 'x') freopen(argv[1],"r",stdin);
    if (argc>2) freopen(argv[2],"w",stdout);
    clock_t cur,prev = clock();
    int numT = 0;
    if (numTestsGiven) {
        scanf("%d",&numT);
        err(">>>Expecting to read %d testcases<<<\n",numT);
    } else {
        err(">>>Reading testcases until end of file or malformed input<<<\n");
    }
    int T = 1;
    while (read_testcase()) {
        err(">>>Solving testcase %d<<<\n",T);
        solve_testcase();
        cur = clock();
        int dur = (cur-prev)*1000/CLOCKS_PER_SEC;
        err("____Case %d done in %dms.\n",T,dur);
        prev = cur; 
        if (T == numT) break; // If !numTestsGiven, then numT == 0 and this will never break
        T++;
    }
}

### Prompt

Your task is to create a cpp solution to 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
///
/// Header; mostly generic
///
#include <cassert>
#include <ctime>
#include <iostream>
#include <cstdio>
#include <vector>
#include <algorithm>
#include <string>


const bool numTestsGiven = false;
const bool debug = true;

using namespace std;
typedef long long ll;

#define err(...) if (debug) fprintf(stderr,__VA_ARGS__)
#define debug(exp) if (debug) cerr << #exp << " = " << (exp) << " "
#define myscanf(exp, num, ...) if (scanf(exp,__VA_ARGS__) != num) return false;

///
/// Testcase variables
///
int n;
const int maxn = 100000;
int p[maxn+1];

vector<pair<int,int> > peaks; // stores lengths of slopes on both sides, larger one first
///
/// Solution
///

void offer(int incs, int decs) {
    if (incs < decs) swap(incs,decs);
    peaks.push_back(pair<int,int>(incs, decs));
}

bool peakCmp(pair<int,int> &a, pair<int,int> &b) {
    if (a.first > b.first) return true;
    if (a.first < b.first) return false;
    return (a.second > b.second);
}

void solve_testcase() {
    peaks.clear();
    // Iterate through all local maxima, and log the lengths of the "slopes" on both sides
    int incs = 0;
    int decs = 0;
    for (int i=2; i<=n; i++) {
        if (p[i] > p[i-1]) {
            if (decs == 0) { // continue an existing up-slope
                incs++;
            } else { // start a new up-slope
                offer(incs,decs);
                decs = 0;
                incs = 1;
            }
        } else { 
            decs++;
        }
    }
    offer(incs,decs);
    sort(peaks.begin(), peaks.end(), peakCmp);

    // Qinghsan wins iff the longest slope has even lenght, is tied with the slope on the otehr side of that peak, and is longer than all other slopes. He has only one winning move in that case.
    if (peaks[0].first % 2 == 0 && peaks[0].first == peaks[0].second) {
        if (peaks.size() == 1 || peaks[0].first > peaks[1].first) printf("1\n");
        else printf("0\n");
    } else {
        printf("0\n");
    }
}

bool read_testcase() {
    cin >> n;
    for (int i=1; i<=n; i++) scanf("%d",p+i);
    return cin.good();
}

///
/// Generic I/O code (not problem-specific)
///

int main(int argc, char **argv) {
    if (argc>1 && argv[1][0]!= 'x') freopen(argv[1],"r",stdin);
    if (argc>2) freopen(argv[2],"w",stdout);
    clock_t cur,prev = clock();
    int numT = 0;
    if (numTestsGiven) {
        scanf("%d",&numT);
        err(">>>Expecting to read %d testcases<<<\n",numT);
    } else {
        err(">>>Reading testcases until end of file or malformed input<<<\n");
    }
    int T = 1;
    while (read_testcase()) {
        err(">>>Solving testcase %d<<<\n",T);
        solve_testcase();
        cur = clock();
        int dur = (cur-prev)*1000/CLOCKS_PER_SEC;
        err("____Case %d done in %dms.\n",T,dur);
        prev = cur; 
        if (T == numT) break; // If !numTestsGiven, then numT == 0 and this will never break
        T++;
    }
}

```