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\le x\le n$) and tells it to Daniel. After that, Daniel chooses another integer index $y$ ($1\le y\le n$, $y \ne 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\le x'\le n$, $|x'-x|=1$, $x'\ne 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\le y'\le n$, $|y'-y|=1$, $y'\ne 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.

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

The second line contains $n$ distinct integers $p_1,p_2,\dots,p_n$ ($1\le p_i\le n$) — the permutation.

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