Binary Search Game

Time limit2sMemory limit64 MB

Summary

Determine whether a player can always guess x within a_x comparison questions given a monotone budget array, and list all valid first questions q.

Level: Hard8 of 10
Topics: Binary search, Greedy, Dynamic programming
Solved: No attempts yet

Problem

Jihak built the following game to teach binary search.

The computer picks an integer $x$ at random with $1 \le x \le n$ and tells the player the value of $n$ .
The player picks an integer $q$ and asks "Is $x$ at most $q$ ?". The computer answers yes or no. The player may ask this question as often as they want, and there is no restriction on the integer $q$ .
Once the player decides that $x$ is known, the player names a guess $v$ and asks "Is $x$ equal to $v$ ?" one time. The computer prints the verdict and the game ends.

Students were learning binary search from this game until Jaehyun told them the optimal strategy in advance, which made the game too easy. Jihak then changed the rule. The computer prints success only when $v = x$ and the number of "Is $x$ at most $q$ ?" questions asked so far is at most $a_x$ , and prints failure otherwise. The final confirmation question is not counted. Jihak likes sorted sequences, so the sequence $a$ satisfies $a_1 \le a_2 \le \cdots \le a_n$ .

Jaehyun could not find a way to always succeed in the changed game and claimed that no such way exists. Jihak could not prove otherwise and asked you for help.

Decide whether there is a way of asking that always succeeds no matter which $x$ the computer picked, and if there is, find every $q$ that may be asked as the first question. A value $q$ may be asked as the first question when there is a way to start with "Is $x$ at most $q$ ?", then choose every later question from the answers received, and succeed for every $x$ .

Input

The first line contains $n$ ( $1 \le n \le 10^6$ ).

The second line contains $n$ integers $a_1, a_2, \ldots, a_n$ ( $1 \le a_1 \le a_2 \le \cdots \le a_n \le 10^9$ ) separated by spaces.

Output

On the first line, print how many values of $q$ may be asked as the first question. If infinitely many such $q$ exist, print inf instead of a count.

On the second line, print those values of $q$ in increasing order, separated by spaces. If no such $q$ exists, or if infinitely many exist, print nothing on the second line.

Examples3

Example 1
Input
```
3
1 2 2
```
Expected output
```
1
1
```
Example 2
Input
```
5
2 2 2 2 2
```
Expected output
```
0
```
Example 3
Input
```
2
3 3
```
Expected output
```
inf
```