균형 잡힌 사진

시간 제한2초메모리 제한512 MB

요약

왼쪽과 오른쪽에서 자기보다 큰 소의 수가 두 배를 넘게 차이 나는 소의 수를 센다.

난이도: 보통10점 중 7점
유형: 이분 탐색, 정렬, 비트 연산
정답자: 아직 제출이 없습니다

문제

농부 존은 사진을 찍으려고 소 $N$ 마리를 한 줄로 세우고 있다 ( $1 \le N \le 100\,000$ ). 줄의 $i$ 번째 소의 키는 $h_i$ 이고, 모든 소의 키는 서로 다르다.

존은 소 사진이 늘 그렇듯 이번 사진도 최대한 보기 좋게 나오기를 바란다. $L_i$ 와 $R_i$ 를 각각 소 $i$ 의 왼쪽과 오른쪽에 있는 소 중 $i$ 보다 키가 큰 소의 수라고 하자. $L_i$ 와 $R_i$ 가 2배를 넘게 차이 나면 소 $i$ 는 "균형이 맞지 않는다". 즉, $L_i$ 와 $R_i$ 중 큰 값이 작은 값의 2배보다 엄격하게 크면 소 $i$ 는 균형이 맞지 않는다. 존은 균형이 맞지 않는 소가 너무 많지 않기를 바란다.

균형이 맞지 않는 소의 수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 $N$ 이 주어진다. 다음 $N$ 개의 줄에 $h_1, \ldots, h_N$ 이 한 줄에 하나씩 주어진다. 각 값은 $1\,000\,000\,000$ 이하의 음이 아닌 정수이다.

출력

균형이 맞지 않는 소의 수를 출력한다.

힌트

예제에서 균형이 맞지 않는 소는 키가 34, 5, 2인 소이다.

예제1

예제 1
입력
```
7
34
6
23
0
5
99
2
```
예상 출력
```
3
```