몬스터 게임

새 비디오 게임이 출시되었다. 이 게임의 세계에는 0부터 N − 1까지 번호가 붙은 N마리의 몬스터가 있다. 각 몬스터는 강함이라는 정숫값을 가진다. 몬스터 i (0 ≤ i ≤ N − 1)의 강함은 Si이다. 몬스터들의 강함은 다음 조건을 만족한다.

• 각 몬스터의 강함은 0 이상 N − 1 이하의 정수이다.
• 서로 다른 두 몬스터의 강함은 같지 않다.

두 몬스터를 골라 서로 싸우게 할 수 있다. 몬스터 a와 몬스터 b (0 ≤ a ≤ N − 1, 0 ≤ b ≤ N − 1, a ≠ b)가 싸우면 결과는 다음과 같이 정해진다.

• |Sa − Sb| = 1이면 강함이 더 작은 몬스터가 이긴다.
• |Sa − Sb| > 1이면 강함이 더 큰 몬스터가 이긴다.

싸움의 결과와 관계없이 같은 몬스터를 원하는 만큼 여러 번 싸우게 할 수 있다.

처음에는 몬스터들의 강함을 모른다. 모든 몬스터의 강함을 알아내려고 한다. 이를 위해 몬스터를 최대 25 000번 싸우게 할 수 있고, 싸움의 결과를 알 수 있다. 또한 싸움 횟수를 최소화하려고 한다.

몬스터의 수가 주어질 때, 몬스터를 여러 번 싸우게 해서 모든 몬스터의 강함을 알아내는 프로그램을 작성하라.

샘플 채점기는 표준 입력에서 다음 데이터를 읽는다.

N
S0 · · · SN−1

프로그램이 성공적으로 종료되면 샘플 채점기는 다음 정보를 표준 출력에 쓴다 (따옴표는 명확성을 위해 붙인 것이다).

• 프로그램이 정답으로 판정되면 함수 Query의 호출 횟수를 “Accepted: 100” 형태로 쓴다.
• 프로그램이 오답으로 판정되면 그 종류를 “Wrong Answer [1]” 형태로 쓴다.

프로그램이 여러 종류의 오답으로 판정되면 샘플 채점기는 그중 하나만 보고한다.

• 4 ≤ N ≤ 1 000.
• 0 ≤ Si ≤ N − 1 (0 ≤ i ≤ N − 1).
• Si ≠ Sj (0 ≤ i < j ≤ N − 1).