Given a sequence of n integer numbers x_{1} … 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_{1} … x_{n}. Assume 0 ≤ n ≤ 10^{5}.
Output
For each case, print the number of indices i that fulfill the condition above.
Input
4 2 3 5 7 4 7 2 5 3 3 -7 -7 -7
Output
1 4 1