#PU693. USACO 2017 January Contest, Gold — Problem 1. Balanced Photo

    ID: 1464 传统题 文件IO:bphoto 2000ms 256MiB 尝试: 0 已通过: 0 难度: 提高+/省选- 上传者: 标签>USACO赛事:jan17来源:usaco.orgscoring:equal_test_cases

USACO 2017 January Contest, Gold — Problem 1. Balanced Photo

USACO 2017 January Contest, Gold — Problem 1. Balanced Photo

题目描述

Farmer John is arranging his NN cows in a line to take a photo (1≤N≤100,0001 \leq N \leq 100,000). The height of the iith cow in sequence is hih_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 ii looks "unbalanced" if LiL_i and RiR_i differ by more than factor of 2, where LiL_i and RiR_i are the number of cows taller than ii on her left and right, respectively. That is, ii is unbalanced if the larger of LiL_i and RiR_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.

输入格式

The first line of input contains NN. The next NN lines contain h1…hNh_1 \ldots h_N, each a nonnegative integer at most 1,000,000,000.

输出格式

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

数据范围

(见题面原文)

样例

样例 1

7
34
6
23
0
5
99
2
3
In this example, the cows of heights 34, 5, and 2 are unbalanced.
Problem credits: Brian Dean