頁面無法載入？點擊這裡可能會修復。
Placeholder

#4001

병아리 사진찍기 2s 512MB

問題

N마리의 병아리들이 사진을 찍기위해 일렬로 나란히 서있는데, i번째 병아리의 키는 h_i이며, 각 병아리의 키는 모두 다르다.

병아리 세계에서는 i번째 병아리의 왼쪽의 병아리들 중 해당 병아리보다 더 키가 큰 병아리의 수를 L_i라고 하고, 오른쪽의 병아리들 중 더 키가 큰 병아리의 수를 R_i라고 하는데, L_i와 R_i가 두 배보다 더 차이가 나면 i번째 병아리가 불균형해 보인다고 한다.

멋진 사진을 찍기 위해 불균형해 보이는 병아리의 수를 알아보자.


輸入

첫 줄에 정수 N이 주어진다. (1 \leq N \leq 100,000)

이어 N줄에 h_1 \ldots h_N가 한 줄에 하나씩 주어진다. (0 \le h_i \le 1,000,000,000)


輸出

불균형해 보이는 병아리의 수를 출력한다.


範例 

7
34
6
23
0
5
99
2
3

각각 34, 5, 2의 키를 갖는 병아리들이 불균형해 보인다.


來源

USACO 2017 January Gold

需要登入才能撰寫程式碼。