Problem Description

In ancient funeral ceremonies, people often invited high monks to perform rituals. After the ritual, there was sometimes a fun program called “high monks duel” to ease the depressing mood.

The general procedure is: first, use grain (usually rice) to “draw” several steps on the ground (representing an $N$-level pagoda). Then, several young monks randomly “stand” on some steps. The highest step must have someone standing on it; the others are optional (as shown in Figure $1$).

Two masters taking part in the game take turns commanding a certain young monk to move upward by any number of steps, but the monk will be blocked by another monk standing on a higher step and cannot pass over them. Two monks cannot stand on the same step, and they also cannot move to lower steps.

The two masters alternate giving commands. In the end, all monks will inevitably be crowded at the upper steps and can no longer move upward. If, when it is a master’s turn to command, no move can be made, the game ends and that master loses.

Given the number of steps and the distribution of monks, compute how the master who moves first should decide to guarantee a win.

Input Format

The input is one line containing $N$ integers separated by spaces, representing the positions of the monks. Step indices start from $1$, so the position of the last monk is the total number of steps. ($N < 100$, total number of steps $< 1000$.)

Output Format

Output one line with two integers $A, B$ separated by a space, meaning to move the monk at position $A$ to position $B$. If there are multiple solutions, output the one with the smaller $A$. If there is no solution, output $-1$.

1 5 9

1 4

1 5 8 10

1 3

Hint

Time limit: 1 second, 64 MB. The 4th Lanqiao Cup National Contest, 2013.

Translated by ChatGPT 5