의자 돌리기
면접 대비시간 제한1초메모리 제한512 MB
각 사람이 불러낸 수 k가 다음 세는 횟수가 되는 요세푸스 제거 과정을 거쳐 마지막에 남는 교수를 출력한다.
문제
Faber College 음악학과의 O'Dagio 교수는 학과장을 뽑는 아주 흥미로운 방식을 고안했다. 음악학과 교수 n명이 한 줄로 서고, 맨 앞에 선 사람이 Faber College의 가장 유명한 동문인 작곡가 I. M. Tondeff의 작품 번호 중 자신이 가장 좋아하는 곡의 번호에 해당하는 정수 k를 외친다. 그러면 학과 교수들은 맨 앞에서 시작해 필요하면 줄의 처음으로 돌아가면서 "세어 나간다". 세는 수가 k에 도달하면 그 사람은 줄에서 빠져나와 그 해의 학과장 직무에서 해방된다(여러 의미로!).
그러면 줄에서 그다음 사람이 자신이 가장 좋아하는 작품 번호를 외치고(이 값이 새로운 k가 된다) 세는 것은 "1"부터 다시 시작하여 다음 사람이 탈락할 때까지 계속된다. 이 과정을 반복해 교수 한 명만 남으면 그 사람이 새 학과장이 된다. 부정행위를 막기 위해 모든 사람의 가장 좋아하는 번호는 미리 공개되며, 아무도 Tondeff의 Opus 1(유명한 술자리 노래 Rhapsody in Brew)을 선택할 수 없다.
예를 들어 교수들이 1번부터 4번까지 번호가 매겨져 그 순서대로 서 있고, 각자가 가장 좋아하는 작품 번호가 차례대로 opus 8(The Four Sneezings), opus 2(Concerto for Kazoo and Cigar Box Banjo), opus 4(The Taekwondo Rondo), opus 2(다시)라고 하자. 그림 F.1은 새 학과장이 선출되는 과정을 보여 준다.
그림 F.1: 선출 과정의 예
입력
입력의 첫 줄에는 교수 수 n(2 ≤ n ≤ 104)이 주어진다. 다음 줄에는 n개의 정수 k1 . . . kn(각 i에 대해 2 ≤ ki ≤ 106)이 주어지며, ki는 i번 교수가 가장 좋아하는 작품 번호다.
출력
새 학과장의 번호를 출력한다.