페이지가 로드되지 않나요? 여기를 눌러보면 고쳐질 수도 있어요.
Placeholder

#8505
서브태스크

눈치게임 1s 1024MB

문제

N명의 친구들이 재미있는 카드 게임을 하고 있다. 게임 진행 방법은 다음과 같다.

  • 친구들이 각각 빈 카드 하나를 받는다.

  • 각자 빈 카드에 1 이상 200,000 이하의 정수 숫자를 쓴다.

  • 친구들이 숫자를 모두 썼다면 카드를 공개하고 승자를 정한다.

승자를 정하는 규칙은 다음과 같다.

  • 공개한 카드 중 여러 번 등장하는 숫자가 있다면 해당 숫자가 적힌 카드를 모두 없앤다.

  • 남은 카드가 없다면 승자는 없다.

  • 남은 카드가 있다면 그 중에서 가장 작은 숫자를 쓴 친구가 이긴다.

게임을 하다 보니 참가한 친구들이 너무 많아져서 승자를 계산하기 쉽지 않다. 친구들이 적은 숫자들이 주어지면 승자를 구하는 프로그램을 작성하여라.


입력

첫 번째 줄에는 눈치게임에 참여한 친구의 수 N이 주어진다. (1 \le N \le 200\,000)

두 번째 줄에는 N개의 정수가 공백을 사이에 두고 주어진다. i번째 정수 C_i는 i번 친구가 공개한 카드의 숫자이다. (1 \le C_i \le 200\,000)


출력

첫 번째 줄에 눈치게임에서 이긴 친구의 번호를 출력한다. 만약 이긴 친구가 없으면 0을 출력한다.


부분문제

번호 점수 조건
#113점

주어진 예제만 채점한다.

#226점

N, C_i \le 1\,000

#322점

모든 C_i의 값이 서로 다르다.

#439점

추가 제약조건은 없다.


예제 #1

5
1 2 3 4 5
1

예제 #2

6
3 12 5 12 5 3
0

예제 #3

20
3 1 4 1 5 9 2 6 5 3 5 8 9 7 9 3 2 3 8 4
8


출처

functionx
로그인해야 코드를 작성할 수 있어요.