Counting problem (3) P84639

Statement

thehtml

Given a sequence of n integer numbers x₁ … x_n, count how many i’s, with 1 ≤ i ≤ n, follow the property

| { j : 1 ≤ j < i ∧ x_j > x_i } | = ⌊ i/2 ⌋ ⁠ ⁠ .

Input

The input consists of several cases. Each case begins with n, followed by the n integer numbers x₁ … x_n. Assume 0 ≤ n ≤ 10⁵.

Output

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