2020 USACO January Bronze
Farmer John is lining up his n cows numbered 1 ... n for a photoshoot. FJ initially planned for the i-th cow from the left to be the cow numbered
ai, and wrote down the permutation
an on a sheet of paper. Unfortunately, that paper was recently stolen by Farmer Nhoj!
Luckily, it might still possible for FJ to recover the permutation that he originally wrote down. Before the sheet was stolen, Bessie recorded the sequence
bn−1 that satisfies
ai+1 for each i (1 ≤ i < n).
Based on Bessie's information, help FJ restore the "lexicographically minimum" permutation a that could have produced b. A permutation x is lexicographically smaller than a permutation y if for some j,
yi for all i < j and
yj (in other words, the two permutations are identical up to a certain point, at which x is smaller than y). It is guaranteed that at least one such a exists.
The first line contains a single integer n (2 ≤ n ≤
103). The second line contains n − 1 space-separated integers
Print the lexicographically minimum permutation
a produces b because 3 + 1 = 4, 1 + 5 = 6, 5 + 2 = 7 and 2 + 4 = 6.
5 4 6 7 6
3 1 5 2 4