Balanced Photo

题目描述

农夫 John 正在将他的 $N$ 头奶牛排成一列来拍照（$1 \leq N \leq 100,000$）。序列中第 $i$ 头奶牛的身高为 $h_i$，且所有奶牛的身高互不相同。

和他给奶牛拍的所有照片一样，FJ 希望这张照片尽可能好看。他规定：若 $L_i$ 与 $R_i$ 相差超过 2 倍，则第 $i$ 头奶牛看起来“失衡（unbalanced）”，其中 $L_i$ 和 $R_i$ 分别表示在她左侧和右侧比她更高的奶牛数量。也就是说，若 $L_i$ 与 $R_i$ 中较大的那个严格大于较小的那个的两倍，则第 $i$ 头奶牛是失衡的。FJ 希望失衡的奶牛不要太多。 请帮助 FJ 计算失衡奶牛的总数。

输入格式

第一行输入 $N$。接下来的 $N$ 行依次输入 $h_1 \ldots h_N$，每个都是不超过 1,000,000,000 的非负整数。

输出格式

请输出失衡奶牛的数量。

7
34
6
23
0
5
99
2

3

提示

在这个例子中，身高为 34、5 和 2 的奶牛是失衡的。 题目来源：Brian Dean

标签: USACO|2017|Gold

来源

USACO|2017|Gold