На выходных Циншань хотела бы пойти со своим другом Даниэлем в поход, но, к сожалению, они — очень занятые школьники, поэтому они могут пойти в поход только на бумаге.
На листочке записана перестановка \(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\) так, чтобы Циншань выигрывала при условии, что оба игрока играют оптимально.
Примечание
В первом тесте Циншань для выигрыша обязана выбрать \(x=3\), поэтому ответ равен \(1\).
Во втором тесте если Циншань выберет \(x=4\), Даниэль может выбрать \(y=1\). На первом ходу (ходит Циншань) Циншань выберет \(x'=3\) и поменяет \(x\) на \(3\). На втором ходу (ходит Даниэль) Даниэль выберет \(y'=2\) и поменяет \(y\) на \(2\). Далее Циншань не сможет выбрать \(x'=2\), потому что \(y=2\) в текущий момент. Поэтому Циншань проиграет.