Crazy old lady#7479
The following problem is a variation of a well known puzzle in the Probability theory. There are seats on a plane and all of the seats are assigned to passengers. Passengers are asked to enter the plane, one at a time, in order of their seats, from to (the passenger that is assigned seat number enters first, next enters the passenger that is assigned seat number , and so on...).
As you might have guessed, queues are too mainstream for a crazy old lady, so she usually goes ahead of everyone and enters first (despite the fact that she might not be assigned the first seat), furthermore she takes some seat that she likes (by chance, it may happen to be her own seat).
After she has taken a seat, the next passengers enter with respect to their seat number (as described above) and take seat as follows:
- if his/her seat is vacant, then he/she takes this seat. - but if his/her seat is already taken, he/she takes any of the remaining seats.
Which seat does the last passenger take? The answer is simple: the last passenger takes either his own seat or the seat of the crazy old lady!
Assume that crazy old lady occupies seat , which is not her own. When passenger that was assigned the seat will enter, he/she will have to take some other seat from a set of free seats. This situation then may repeat with next passengers. But when some passenger take the seat of crazy old lady, obviously (!) all of the following passengers take their own seats. In this problem we would like to know the original seat of crazy old lady.
May contain several tests. First line of Input contains the number of tests (1 \leq t \leq 10). Each of the next lines contains n + 1 numbers, separated by space, first is (1 \leq n \leq 10^3), then numbers follow: the seats taken by passengers in order of their entrance (p_1, p_2, ..., p_n - where p_i means that the passenger that was -th to enter took seat p_i). Input is guaranteed to be correct, i.e. to satisfy conditions of the problem statement.
Output the seat of crazy old lady, if it can be determined uniquely, otherwise, output .
Example 1
In case 2 2 1 we cannot determine the answer uniquely, since passenger could be the crazy old lady who took someone else's seat, and passenger could also be the crazy old lady who sat in her own seat.