Balanced Photo#10550
Farmer John is arranging his cows in a line to take a photograph. The height of the -th cow in the line is h_i, and all cow heights are distinct.
As with all photographs of his cows, FJ wants this one to look as nice as possible. He considers cow to be "unbalanced" if L_i and R_i differ by a factor of more than , where L_i and R_i are the numbers of cows taller than cow to her left and right, respectively. In other words, cow is unbalanced if the larger of L_i and R_i is strictly greater than twice the smaller of the two.
FJ is hoping that not too many of his cows are unbalanced.
Please help FJ determine the total number of unbalanced cows.
The first line contains n~(1 \le n \le 10^5). The next lines contain h_1, \ldots, h_n, where each h_i is a nonnegative integer at most 10^9.
Print the number of cows that are unbalanced.
In this example, the cows with heights , and are unbalanced.
Example 1