Let's Go Hiking

题意翻译

两个人（下简称 `Q` 和 `D` ）取爬山，我们可以把这座山看作一个长度为 $n$ 的排列，其中 $p_i$ 表示 $i$ 处的高度。 `Q` 会先选择一个位置 $x_0$ ，并把这个位置告诉 `D` 。在此之后，`D` 会选择一个位置 $y_0$ 。 接下来两个人开始轮流爬山， `Q` 先行动，他们的行动遵循如下规则： - 如果是 `Q` 行动，假设此时她在 $x$ 处，`D` 在 $y$ 处，则她下一步移动到的位置 $x'$ 必须满足 $1\le x'\le n\ ,\ |x'-x|=1\ ,\ x'\neq y\ ,\ p_{x'}<p_x$ 。 - 如果是 `D` 行动，假设此时他在 $y$ 处，`Q` 在 $x$ 处，则他下一步移动到的位置 $y'$ 必须满足 $1\le y'\le n\ ,\ |y'-y|=1\ ,\ y'\neq x\ ,\ p_{y'}>p_y$ 。 当某一个人不能行动时，对方获胜。 假设两个人绝顶聪明，求出 `Q` 能选出多少个初始位置 $x_0$ ，保证她必胜。 $2\le n\le 10^5\ ,\ 1\le p_i\le n$，保证 $p_i$ 是一个排列。

题目描述

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.

输入输出样例

输入样例 #1

5
1 2 5 4 3

输出样例 #1

1

输入样例 #2

7
1 2 4 6 5 3 7

输出样例 #2

0

说明

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.