Counting problem (3) P84639

Statement

Given a sequence of $n$ integer numbers $x_1 \dots x_n$ , count how many $i$ ’s, with $1 \le i \le n$ , follow the property

$\vert \{ j : 1 \le j < i \wedge x_j > x_i \} \vert = \lfloor i/2 \rfloor \enspace .$

Input

The input consists of several cases. Each case begins with $n$ , followed by the $n$ integer numbers $x_1 \dots x_n$ . Assume $0 \le n \le 10^5$ .

For each case, print the number of indices $i$ that fulfill the condition above.

Public test cases

Input

4   2 3 5 7
4   7 2 5 3
3   -7 -7 -7

Output

1
4
1

Information