Let's Go Hiking
Contest: Codeforces Round 706 (Div. 1)
Difficulty rating: 1900
Tags: games, greedy

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.

Input format:
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.

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

Constraints:
Time limit: 1.0 s
Memory limit: 256.0 MB

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.

Example input:
5
1 2 5 4 3

Example output:
1

Example input:
7
1 2 4 6 5 3 7

Example output:
0

Editorial:
Let's consider that the $$$2k+1(k\ge 0)$$$-th turn is Qingshan's and the $$$2k+2(k\ge 0)$$$-th turn is Daniel's.
If Qingshan chooses $$$x(1<x\le n)$$$ satisfying $$$x=n$$$ or $$$p_x<p_{x+1}$$$, then Daniel can choose $$$y=x-1$$$ to make Qingshan can't move in the first turn. The case that $$$x=1$$$ or $$$p_x<p_{x-1}$$$ is the same. So Qingshan must choose $$$x(1<x<n)$$$ satisfying $$$p_x>p_{x-1}$$$ and $$$p_x>p_{x+1}$$$ at first.
Let $$$l$$$ be the length of the longest monotone segments and $$$c$$$ be the number of the longest monotone segments. $$$l\ge 2$$$ and $$$c\ge 1$$$ are always true.
It is obvious that Qingshan can't win when $$$c>2$$$ because wherever Qingshan chooses, Daniel can always find a place that he can move $$$l-1$$$ times while Qingshan can move $$$l-1$$$ times at most.
When $$$c=1$$$, Qingshan will also lose. If the only longest monotone segment is $$$p_s,p_{s+1}\dots,p_{s+l-1}$$$ and it's increasing(if it's decreasing, the discussion is almost the same). Qingshan must choose $$$x=s+l-1$$$ at first. The discussion follows:
• If $$$l\bmod 2=0$$$, Daniel can choose $$$y=s$$$ at first. After the $$$l-3$$$-th turn(Qingshan's turn), $$$x=s+l-\frac{l}{2}$$$ and After the $$$l-2$$$-th turn(Daniel's turn), $$$y=s+\frac{l}{2}-1$$$. The next turn is Qingshan's and Qingshan loses.
• If $$$l\bmod 2=1$$$, Daniel can choose $$$y=s+1$$$ at first. Pay attention that Qingshan can't change $$$x$$$ to $$$x+1$$$ in the first turn because Daniel can move $$$l-2$$$ times while Qingshan can move $$$l-2$$$ times at most if she change $$$x$$$ to $$$x+1$$$ in the first turn. After the $$$l-4$$$-th turn(Qingshan's turn), $$$x=s+l-\frac{l-1}{2}$$$ and After the $$$l-3$$$-th turn(Daniel's turn), $$$y=s+\frac{l-1}{2}$$$. The next turn is Qingshan's and Qingshan loses.
When $$$c=2$$$ , the only two longest monotone segments must be like $$$p_{m-l+1}<p_{m-l+2}<\cdots<p_m>p_{m+1}>\cdots>p_{m+l-1}$$$. (Otherwise Qingshan will lose.) In that case Qingshan will lose if $$$l\bmod 2=0$$$ because Daniel can choose $$$y=m-l+1$$$ at first and whatever Qingshan's first move is, Qingshan will lose(just like the discussion above). If $$$l\bmod 2=1$$$, Qingshan is the winner. It is not hard to check it in $$$O(n)$$$.
The overall time complexity is $$$O(n)$$$.