13121번 - 이진 탐색

지학이는 학생들에게 이진 탐색을 가르쳐주기 위해서 간단한 게임을 만들었다. 이 게임은 다음과 같은 과정으로 진행된다.

1. 먼저 컴퓨터가 1 이상 n 이하의 정수 x를 무작위로 하나 정하고, 플레이어에게 n의 값을 알려준다.
2. 그 다음, 플레이어는 정수 q를 하나 정해서, 컴퓨터에게 “x가 q 이하입니까?”라는 질문을 원하는 만큼 한다. 질문할 때마다 컴퓨터는 ‘예’ 또는 ‘아니오’로 답해준다. 플레이어의 목적은 가능한 한 질문을 적게 하여, x의 값을 알아내는 것이다.
3. 플레이어가 자신이 x의 값을 알아냈다고 판단한다면, 플레이어가 추측한 x의 값을 v라고 할 때, 컴퓨터에게 “x의 값이 v입니까?”라는 질문을 단 한 번 할 수 있다. 컴퓨터는 플레이어가 추측한 x의 값이 정확하다면 ‘성공’을, 정확하지 않다면 ‘실패’를 출력하고, 게임을 종료한다.

지학이는 수업 시간에 자신이 만든 게임을 하며 이진 탐색을 이해하는 학생들을 보며 뿌듯함을 느꼈다. 그런데 어느 날, 수업 준비를 하던 지학이는 충격적인 소식을 접했다. 지학이의 게임 설명을 들은 재현이가 ‘게임이 너무 쉽다’며 학생들에게 최적의 방법을 미리 알려주었다는 것이다. 자신이 열심히 구현한 게임이 모두 무용지물이 되어 버렸다는 생각에 화가 난 지학이는, 재현이가 먹던 허니버터칩을 뺏는 정도의 복수로는 분을 풀 수 없겠다고 생각하여, 재현이에게 추가 과제를 내 주기로 하였다.

지학이는 게임을 약간 고쳐서, 컴퓨터가 정한 수가 x일 때, 플레이어가 추측한 수가 정확할 뿐만 아니라 그 때까지 한 질문의 수가 a_x번 이하일 때에만 ‘성공’이라고 출력하고, 그렇지 않을 때에는 ‘실패’라고 출력하도록 게임을 바꿔버렸다. 그리고 지학이는 정렬된 수열이 아름답다고 생각하기 때문에, 수열 {a_x} 가 단조증가하도록(즉, a₁ ≤ a₂ ≤ · · · ≤ a_n을 만족하도록) 하였다. 재현이에게 주어진 추가 과제는, 이렇게 지학이가 바꾼 게임이 컴퓨터가 정한 x의 값과 관계없이 항상 ‘성공’을 출력하도록 하는 질문을 하는 방법을 찾는 것이다.

숙제를 받을 때만 해도 자신만만하던 재현이는, 게임을 몇 번 시도해보다가, 해답을 찾지 못하자, 지학이에게 ‘그런 방법은 없다’고 주장하며 강력하게 항의했다. 이에 지학이는 그런 방법이 존재함을 증명하려고 했으나, 사실 이 숙제는 지학이가 재현이에게 복수하기 위해 대충 만든 것이었기에 지학이도 아는 게 별로 없었고, 결국 증명에 실패하였다.

어떻게든 증명을 해내고 싶었던 지학이는 당신에게 도움을 요청하였다. 당신이 해야 할 일은, 지학이가 바꾼 게임에서 컴퓨터가 항상 ‘성공’을 출력하도록 하는 방법이 있는지를 확인하고, 존재한다면 첫 번째 질문으로 물어봐도 되는 q의 값을 모두 구하는 것이다.

첫 번째 줄에 n(1 ≤ n ≤ 1 000 000)이 주어진다.

두 번째 줄에 n개의 정수 a₁, a₂, . . . , a_n(1 ≤ a₁ ≤ a₂ ≤ . . . ≤ a_n ≤ 10⁹)이 공백을 사이에 두고 주어진다.

첫 번째 줄에, 첫 번째 질문으로 물어봐도 되는 q의 가짓수를 출력한다. 단, 첫 번째 질문으로 물어봐도 되는 q가 무한히 많다면 “inf”(따옴표 제외)를 대신 출력한다.

두 번째 줄에는, 첫 번째 질문으로 물어봐도 되는 q의 값들을 공백을 사이에 두고 오름차순으로 출력한다. 단, 첫 번째 질문으로 물어봐도 되는 q가 0개이거나 무한히 많다면 아무것도 출력하지 않아야 한다.