Farmer John has a permutation p of length N (2 \leq N \leq 10^5), containing each positive integer from 1 to N exactly once. However, Farmer Nhoj has broken into FJ's barn and disassembled p. To not be too cruel, FN has written some hints that will help FJ reconstruct p. While there is more than one element remaining in p, FN does the following:

Let the remaining elements of p be p'_1, p'_2, \dots , p'_n,

If p'_1 > p'_n, he writes down p'_2 and removes p'_1 from the permutation.
Otherwise, he writes down p'_{n-1} and removes p'_n from the permutation.

At the end, Farmer Nhoj will have written down N - 1 integers h_1, h_2, \dots, h_{N-1}, in that order. Given h, Farmer John wants to enlist your help to reconstruct the lexicographically minimum p consistent with Farmer Nhoj's hints, or determine that Farmer Nhoj must have made a mistake. Recall that if you are given two permutations p and p', p is lexicographically smaller than p' if p_i < p'_i at the first position i where the two differ.

#8170 upload 1 done 1 how_to_reg 1 call_split Subtask

Farmer John's Favorite Permutation timer 1s memory 1024MB

#8170
Subtask

Farmer John's Favorite Permutation 1s 1024MB