周末,青山建议她和朋友丹尼尔去爬山。不幸的是,他们是忙碌的高中生,所以他们只能在草稿纸上徒步旅行。
排列 $$$p$$$ 从左到右写在纸上。首先青山选择一个整数索引$$$x$$$ ($$$1\le x\le n$$$) 并告诉Daniel。之后,Daniel 选择另一个整数索引 $$$y$$$ ($$$1\le y\le n$$$, $$$y \ne x$$$)。
游戏轮流进行,和往常一样,青山先走。规则如下:
- 如果轮到青山,青山必须将 $$$x$$$ 更改为索引 $$$x'$$$,同时满足 $$$1\le x'\le n$$$、$$$|x'-x|=1$$$、$$$x'\ne y$$$ 和 $$$p_{x'}<p_x$$$。
- 如果轮到 Daniel,Daniel 必须将 $$$y$$$ 更改为索引 $$$y'$$$,同时满足 $$$1\le y'\le n$$$、$$$|y'-y|=1$$$、$$$y'\ne x$$$ 和 $$$p_{y'}>p_y$$$。
不能让她或他走一步的人就输了,另一个人就赢了。作为青山的粉丝,你需要计算在双方都发挥最佳的情况下,有多少个$$$x$$$ 可以让青山获胜。
输入
第一行包含一个整数 $$$n$$$ ($$$2\le n\le 10^5$$$) — 排列的长度。
第二行包含 $$$n$$$ 不同的整数 $$$p_1,p_2,\dots,p_n$$$ ($$$1\le p_i\le n$$$) — 排列。
输出
打印青山可以选择的$$$x$$$可能值的个数,以使其获胜。
示例
输入 #1
5 1 2 5 4 3
输出 #1
1
输入 #2
7 1 2 4 6 5 3 7
输出 #2
0
注意
第一个测试用例中,青山只能选择$$$x=3$$$获胜,所以答案是$$$1$$$。
在第二个测试用例中,如果青山会选择$$$x=4$$$,那么大牛可以选择$$$y=1$$$。在第一回合(青山的)青山选择$$$x'=3$$$并将$$$x$$$更改为$$$3$$$。在第二回合(丹尼尔的)丹尼尔选择$$$y'=2$$$并将$$$y$$$更改为$$$2$$$。青山不能选择$$$x'=2$$$,因为此时$$$y=2$$$。那么青山就输了。