Ankica's Stone Game

Ankica and Branko are playing a modified stone game. There are \(N\) piles of stones; the \(i\)th pile has \(a_i\) stones. The players alternate moves. In each move one player removes a positive number of stones from one chosen pile (at most all stones in that pile) so that the player who takes the last stone wins.

The twist is that in each turn the pile from which stones are removed is predetermined by the other player. The game proceeds as follows, with rounds numbered starting from 1 and increasing by 1 each time:

• Odd rounds: Branko specifies a non-empty pile (i.e. gives an index \(k\) with \(1\le k\le N\) such that the \(k\)th pile is non-empty). Then Ankica must remove between 1 and all stones from that pile. Let \(s_k\) denote the number of stones in that pile at that moment.
• Even rounds: Ankica specifies a non-empty pile (i.e. an index \(k\) with \(1\le k\le N\)). Then Branko removes between 1 and all stones from that pile (which has \(s_k\) stones at that moment).

It is known that the initial configuration is chosen so that Ankica always has a winning strategy. In fact, by playing as follows, Ankica can guarantee victory:

1. Whenever forced to move (odd rounds), remove all stones from the designated pile.
2. On the even rounds when choosing a pile for Branko, always choose a non-empty pile (for example, the one with the smallest index).

If you are Ankica, can you ensure victory? You must write an interactive program that plays as Ankica and guarantees her win.

Interaction

The interaction is as follows. First, your program reads the initial state from standard input. The first line contains an integer \(N\). The second line contains \(N\) space‐separated integers \(a_1,a_2,\dots,a_N\) which denote the number of stones in each pile.

Then the game begins. The rounds are handled as follows:

• Odd rounds:
  • Your program first reads an integer \(k\). If all piles are empty then \(k = -1\) and you must terminate your program (Ankica has lost if this happens).
  • Otherwise, \(k\) (\(1\le k\le N\)) indicates that you must remove stones from the \(k\)th (non-empty) pile which contains \(s_k\) stones. Your program should output an integer from the interval \([1,s_k]\) indicating the number of stones to remove, and then flush the output.
• Even rounds:
  • Your program first outputs an integer \(k\) (flush the output). If all piles are empty then \(k = -1\) and you must terminate (Ankica wins).
  • Otherwise, \(k\) (\(1\le k\le N\)) indicates the pile from which Branko must remove stones (this pile is non-empty and has \(s_k\) stones). Your program then reads an integer from the interval \([1,s_k]\) representing the number of stones Branko removes.

It is guaranteed that the initial configuration is such that no matter how Branko plays, Ankica has a winning strategy.

Sample Interaction 1

Ankica/Branko	Input / Output	Explanation
(Initial Input)	1 4	There is one pile with 4 stones.
Branko (odd round)	1	Branko specifies pile 1.
Ankica (odd round)	4	Ankica removes all 4 stones from pile 1.
Ankica (even round)	-1	All piles empty, Ankica outputs -1 and wins.

Sample Interaction 2

Ankica/Branko	Input / Output	Explanation
(Initial Input)	3 1 1 5	Three piles with 1, 1 and 5 stones respectively.
Branko (odd round)	3	Branko specifies pile 3 (which has 5 stones).
Ankica (odd round)	5	Ankica removes all 5 stones from pile 3.
Ankica (even round)	1	Ankica specifies pile 1 for Branko.
Branko (even round)	1	Branko removes the only stone from pile 1.
Branko (odd round)	2	Branko forces move on pile 2 (only 1 stone remains).
Ankica (odd round)	1	Ankica removes the stone from pile 2.
Ankica (even round)	-1	No stones remain, Ankica outputs -1 and wins.

inputFormat

The input begins with two lines. The first line contains an integer \(N\) (the number of piles). The second line contains \(N\) space-separated integers \(a_1, a_2, \dots, a_N\), where \(a_i\) is the number of stones in the \(i\)th pile. Then, during the game, further input is provided as described in the interaction section.

outputFormat

Your program should output one integer at each of your turns as described (with a flush after each output). On odd rounds, output the number of stones (an integer in the interval \([1,s_k]\)) to remove from the forced pile. On even rounds, output the index of the pile (an integer between 1 and \(N\), or -1 if no pile is available) that Branko must play on. When no moves remain, output -1 and terminate the program.

sample

1
4
1

4
-1

</p>