题目描述

Farmer John is arranging his $N$ cows in a line to take a photo ($1 \leq N \leq 100,000$). The height of the $i$th cow in sequence 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. He decides that cow $i$ looks "unbalanced" if $L_i$ and $R_i$ differ by more than factor of 2, where $L_i$ and $R_i$ are the number of cows taller than $i$ on her left and right, respectively. That is, $i$ is unbalanced if the larger of $L_i$ and $R_i$ is strictly more than twice the smaller of these two numbers. FJ is hoping that not too many of his cows are unbalanced.

Please help FJ compute the total number of unbalanced cows.

FJ 正在安排他的 $N$ 头奶牛站成一排来拍照（$1\le N \le 10^5$）。序列中的第 $i$ 头奶牛的高度是 $h_i$，且序列中所有的奶牛的身高都不同。

就像他的所有牛的照片一样，FJ希望这张照片看上去尽可能好。他认为，如果 $L_i$ 和 $R_i$ 的数目相差 $1$ 倍以上，第 $i$ 头奶牛就是不平衡的（$L_i$ 和 $R_i$ 分别代表第 $i$ 头奶牛左右两边比她高的奶牛的数量）。也就是说，如果 $L_i$ 和 $R_i$ 中的较大数大于较小数的 $2$ 倍，第 $i$ 头奶牛就是不平衡的。FJ 不希望他有太多的奶牛不平衡。

请帮助 FJ 计算不平衡的奶牛数量。

输入格式

The first line of input contains $N$. The next $N$ lines contain $h_1 \ldots h_N$, each a nonnegative integer at most 1,000,000,000.

第一行一个整数 $N$。

接下 $N$ 行包括 $H_1$ 到 $H_n$，每行一个不超过 $10^9$ 的非负整数。

输出格式

Please output a count of the number of cows that are unbalanced.

请输出不平衡的奶牛数量。

7
34
6
23
0
5
99
2

3

提示

感谢 @XY星系质量PK 的翻译