TAP2014J - Distracted judges

no tags 

[ The original version of this problem (in Spanish) can be found at http://dc.uba.ar/events/icpc/download/problems/tap2014-problems.pdf ]

This problem was included in this contest at the last minute, replacing another one that the jury could not fully prepare in time. We will not tell you much about the original problem because we will use it for the contest next year. We will only say that it was called "Playing with lists" because it deals with integer lists. The input for the problem was formed by L lists of integers, and its format was:

- a line with an integer N1 indicating the amount of numbers in the first list;

- N1 lines each representing an integer in the first list;

- a line with an integer N2 indicating the amount of numbers in the second list;

- N2 lines each representing an integer in the second list;

... 

- a line with an integer NL indicating the amount of numbers in the last list;

- NL lines each representing an integer in the last list.

In an unfortunate accident, Joaquin -a member of the jury- erased the first line of each input file (the one which contains N1). We need your help to restore the input files so we can use the problem next year. Given the file without the first line, we ask you to tell us which are the possible values of N1 such that, if we add a line with that value at the beginning, the resulting file will be a valid input according to the description given above.

This problem was included in this contest at the last minute, replacing another one that the jury could not fully prepare in time. We will not tell you much about the original problem because we will use it for the contest next year. We will only say that it was called "Playing with lists" because it deals with integer lists. The input for the problem was formed by L lists of integers, and its format was:
* a line with an integer N_1 indicating the amount of numbers in the first list;
* N_1 lines each representing an integer in the first list;
* a line with an integer N_2 indicating the amount of numbers in the second list;
* N_2 lines each representing an integer in the second list;
... 
* a line with an integer N_L indicating the amount of numbers in the last list;
* N_L lines each representing an integer in the last list.
In an unfortunate accident, Joaquin -a member of the jury- erased the first line of each input file (the one which contains N_1). We need your help to restore the input files so we can use the problem next year. Given the file without the first line, we ask you to tell us which are the possible values of N_1 such that, if we add a line with that value at the beginning, the resulting file will be a valid input according to the description given above.

 

Input

The first line contains an integer T (1 ≤ T  105) which indicates the number of lines remaining in the input file. Each of the next T lines contains an integer Ri which represents the number left on the i-th line of the input file after the accident ( Ri  105 for i = 1, 2, ... , T). 

 

Output

Print a line for each possible value of N1. Print all possible answers in increasing order.

 

Example 1

Input:
5
3
1
2
4
5

Output:
2
5

Example 2

Input:
10
1
2
3
4
5
6
7
8
9
10

Output:
1
4
10

hide comments
Vipul Srivastava: 2015-06-28 23:18:33

the output for
2
1
2
is 2
Got one WA due to such cases.

Last edit: 2015-06-28 23:19:59
CoNtRaDiCtIoN: 2015-06-14 09:52:40

for those getting wa try this
2
1
2

Maroof: 2015-06-13 08:32:28

Was using 5000 instead of 10^5 as array size and got 3 SISGEVs . :(

DHEERAJ KUMAR: 2015-06-12 00:36:40

Nice problem :) a bit silly mistake costed me 1 WA

Rishabh Joshi: 2015-02-20 16:25:39

Easy! think simple..


Added by:Fidel Schaposnik
Date:2014-09-29
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64
Resource:Argentinian Programming Tournament 2014