Unbalanced Cows Photo

Farmer John is arranging his N cows in a line for a photo (\(1 \leq N \leq 100000\)). The height of the \(i\)th cow is \(h_i\), and all heights are distinct.

A cow \(i\) is said to be unbalanced if the number of cows taller than \(i\) on her left (\(L_i\)) and on her right (\(R_i\)) differ by more than a factor of 2. In other words, if \[ \max(L_i, R_i) > 2\min(L_i, R_i), \] where if either \(L_i\) or \(R_i\) is zero (and the other is nonzero), the inequality holds. If both are zero then the cow is balanced.

Help Farmer John compute the total number of unbalanced cows.

inputFormat

The first line contains an integer \(N\), the number of cows. The next \(N\) lines (or one line with \(N\) space‐separated integers) each contain a distinct integer representing the height \(h_i\) of the \(i\)th cow.

outputFormat

Output a single integer: the total number of unbalanced cows.

sample

6
10 3 7 1 5 8

2