Description

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需要你告诉他有多少头牛不平衡。

Format

Input

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

Output

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

输出有多少头牛是不平衡的

Samples

7
34
6
23
0
5
99
2

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