#4759. [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.
The first line of input contains N. The next NN lines contain h1…hN
each a nonnegative integer at most 1,000,000,000.
Please output a count of the number of cows that are unbalanced.
BZPRO Powered by