레이팅 미적용설명
\(N\)명의 아이들이 식탁에서 점심을 먹고 있다. 아이들은 차례로 식탁에서 음식을 가져간다.
일부 아이들은 아직 예의를 제대로 배우지 못해서 다른 아이들에게 기회를 주지 않고 음식에 달려든다. 어느 순간 어떤 아이가 음식 한 조각을 가져갔는데, 그 아이가 이미 (새로 가져간 조각을 제외하고) 나머지 아이들 전부를 합친 것보다 많은 음식을 가져간 상태였다면, 엄마는 그 아이에게 얌전히 굴라고 주의를 준다.
아이들이 음식을 가져가는 순서가 주어진다. 엄마가 아이들에게 주의를 몇 번 주어야 하는지 계산하는 프로그램을 작성하시오.
제약
입력 형식
입력의 첫째 줄에 아이들이 가져가는 음식 조각의 개수인 정수 \(N\) (\(1 \le N \le 100\,000\))이 주어진다.
다음 \(N\)개의 줄에는 음식 한 조각을 가져간 아이의 이름이 주어진다. 이름은 영어 알파벳 소문자 최대 \(20\)자의 문자열이다.
출력 형식
주의를 준 횟수를 한 줄에 출력한다.
서브태스크
| 서브태스크 | 점수 | 설명 |
|---|---|---|
Subtask 1 | 20점 |
예제 1
입력
4
mirko
stanko
stanko
stanko출력
1예제 2
입력
17
a
b
b
a
a
a
c
a
b
b
c
b
b
b
b
b
b출력
4문제 정보
태그