8759: BZOJ4759：[Usaco2017 Jan]Balanced Photo

Farmer John is arranging his N cows in a line to take a photo (1≤N≤100,000). The height of the iit h cow in sequence is hihi, and the heights of all cows are distinct.As with all photographs of his c ows, FJ wants this one to come out looking as nice as possible. He decides that cow ii looks "unbala nced" if Li and RRi differ by more than factor of 2, where LiLi and RiRi are the number of cows tall er than i on her left and right, respectively. That is, ii is unbalanced if the larger of Li and Ri  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. 农夫约翰正在安排他的N头牛拍照片， 每头牛有一个身高，从1到N编号，排列成一行(h1,h2...hn)，每头牛i左边 比他高的牛的数量记为Li，右边比他高的牛的数量记为Ri，如果存在i满足max(Ri,Li)>2*min(Li,Ri)则这个牛i是 不平衡的，现在FJ需要你告诉他有多少头牛不平衡。

输入格式

The first line of input contains N. The next NN lines contain h1…hN each a nonnegative integer at most 1,000,000,000. 输入第一行为N(N<=1e5)，接下来的一行有N个数，每个数表示第i头牛的身高，不超过1e9

输出格式

Please output a count of the number of cows that are unbalanced. 输出有多少头牛是不平衡的

样例输入

7
34
6
23
0
5
99
2

样例输出

3
//在这个样例中，身高为34，5,2的牛是不平衡的

提示

没有写明提示

题目来源

Gold