Balanced Photo

Time limit2sMemory limit512 MB

Summary

Count cows whose taller neighbors on the left and right differ by more than a factor of two.

Level: Medium7 of 10
Topics: Binary search, Sorting, Bit manipulation
Solved: No attempts yet

Problem

Farmer John is arranging his $N$ cows in a line to take a photo ( $1 \le N \le 100\,000$ ). The height of the $i$ -th cow in the line is $h_i$ , and the heights of all cows are distinct.

As with all photographs of his cows, FJ wants this one to come out looking as nice as possible. Let $L_i$ and $R_i$ be the number of cows taller than cow $i$ on her left and on her right, respectively. Cow $i$ looks "unbalanced" if $L_i$ and $R_i$ differ by more than a factor of 2. That is, cow $i$ is unbalanced if the larger of $L_i$ and $R_i$ is strictly more than twice the smaller of the two. FJ hopes that not too many of his cows are unbalanced.

Compute the total number of unbalanced cows.

Input

The first line contains $N$ . Each of the next $N$ lines contains one of $h_1, \ldots, h_N$ , in order. Each value is a nonnegative integer at most $1\,000\,000\,000$ .

Output

Print the number of unbalanced cows.

Hint

In the sample, the cows of heights 34, 5, and 2 are unbalanced.

Examples1

Example 1
Input
```
7
34
6
23
0
5
99
2
```
Expected output
```
3
```