Counting problem (3) P84639


Statement
 

pdf   zip

thehtml

Given a sequence of n integer numbers x1xn, count how many i’s, with 1 ≤ in, follow the property

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

Input

The input consists of several cases. Each case begins with n, followed by the n integer numbers x1xn. Assume 0 ≤ n ≤ 105.

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
    Author
    Salvador Roura
    Language
    English
    Official solutions
    C++
    User solutions
    C++