Qingshan recommends that she and her companion Daniel go climbing. Shockingly, they are occupied secondary school understudies, so they can just go climbing on scratch paper. A stage p is composed from left to directly on the paper. First Qingshan picks an integer list x (1≤x≤n) and tells it to Daniel. From that point onward, Daniel picks
Correct answer will be upvoted else downvoted. Computer science.
Qingshan recommends that she and her companion Daniel go climbing. Shockingly, they are occupied secondary school understudies, so they can just go climbing on scratch paper.
A stage p is composed from left to directly on the paper. First Qingshan picks an integer list x (1≤x≤n) and tells it to Daniel. From that point onward, Daniel picks another integer file y (1≤y≤n, y≠x).
The game advances turn by turn and of course, Qingshan moves first. The principles follow:
In case it is Qingshan's move, Qingshan should change x to such a record x′ that 1≤x′≤n, |x′−x|=1, x′≠y, and px′<px simultaneously.
In case it is Daniel's move, Daniel should change y to such a record y′ that 1≤y′≤n, |y′−y|=1, y′≠x, and py′>py simultaneously.
The individual who can't take her or his action loses, and different successes. You, as Qingshan's fan, are approached to compute the number of conceivable x to make Qingshan win for the situation the two players play ideally.
Input
The primary line contains a solitary integer n (2≤n≤105) — the length of the change.
The subsequent line contains n unmistakable integers p1,p2,… ,pn (1≤pi≤n) — the change.
Output
Print the number of potential upsides of x that Qingshan can decide to make her success.
Step by step
Solved in 3 steps with 1 images
