B. Идем в поход!
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

На выходных Циншань хотела бы пойти со своим другом Даниэлем в поход, но, к сожалению, они — очень занятые школьники, поэтому они могут пойти в поход только на бумаге.

На листочке записана перестановка $$$p$$$. Сначала Циншань выбирает индекс $$$x$$$ ($$$1\le x\le n$$$) и сообщает его Даниэлю. После этого Даниэль выбирает другой индекс $$$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$$$.
  • В свой ход Даниэль должен изменить значение $$$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$$$ в начале игры так, чтобы выигрывала Циншань.

Примеры
Входные данные
5
1 2 5 4 3
Выходные данные
1
Входные данные
7
1 2 4 6 5 3 7
Выходные данные
0
Примечание

В первом тесте Циншань для выигрыша обязана выбрать $$$x=3$$$, поэтому ответ равен $$$1$$$.

Во втором тесте если Циншань выберет $$$x=4$$$, Даниэль может выбрать $$$y=1$$$. На первом ходу (ходит Циншань) Циншань выберет $$$x'=3$$$ и поменяет $$$x$$$ на $$$3$$$. На втором ходу (ходит Даниэль) Даниэль выберет $$$y'=2$$$ и поменяет $$$y$$$ на $$$2$$$. Далее Циншань не сможет выбрать $$$x'=2$$$, потому что $$$y=2$$$ в текущий момент. Поэтому Циншань проиграет.