|Codeforces Round #706 (Div. 1)|
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:
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.
5 1 2 5 4 3
7 1 2 4 6 5 3 7
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.