레이팅 미적용설명
농부 존은 사진을 찍기 위해 \(N\)마리의 소를 한 줄로 세우고 있다 (\(1 \leq N \leq 100,000\)). 줄에서 \(i\)번째 소의 키는 \(h_i\)이고, 모든 소의 키는 서로 다르다.
소들의 사진이 늘 그렇듯, FJ는 이번 사진도 최대한 보기 좋게 나오기를 바란다. FJ는 소 \(i\)의 왼쪽과 오른쪽에서 \(i\)보다 키가 큰 소의 수를 각각 \(L_i\)와 \(R_i\)라 할 때, \(L_i\)와 \(R_i\)가 2배 넘게 차이 나면 소 \(i\)가 "불균형"하다고 정한다. 즉, \(L_i\)와 \(R_i\) 중 큰 값이 작은 값의 두 배보다 확실히(strictly) 크면 \(i\)는 불균형하다. FJ는 불균형한 소가 너무 많지 않기를 바라고 있다.
FJ가 불균형한 소의 총수를 계산할 수 있도록 도와주자.
문제 출처: Brian Dean
제약
문제 출처: Brian Dean
입력 형식
입력의 첫째 줄에 \(N\)이 주어진다. 다음 \(N\)개의 줄에 \(h_1 \ldots h_N\)이 주어지며, 각각은 1,000,000,000 이하의 음이 아닌 정수이다.
출력 형식
불균형한 소의 수를 출력한다.
Standard input / output
This problem is judged over standard input/output. The original contest used named files — if you prefer the classic interface, tick “File I/O” on the submit form and read/write these files instead:
입력을 읽을 파일
bphoto.in · 출력을 쓸 파일 bphoto.out예제 1
입력
7
34
6
23
0
5
99
2출력
3설명
In this example, the cows of heights 34, 5, and 2 are unbalanced.
문제 정보
태그