#PU988. USACO 2020 January Contest, Bronze — Problem 2. Photoshoot
USACO 2020 January Contest, Bronze — Problem 2. Photoshoot
USACO 2020 January Contest, Bronze — Problem 2. Photoshoot
题目描述
Farmer John is lining up his cows (), numbered , for a photoshoot. FJ initially planned for the -th cow from the left to be the cow numbered and wrote down the permutation on a sheet of paper. Unfortunately, that paper was recently stolen by Farmer Nhoj! Luckily, it might still be possible for FJ to recover the permutation that he originally wrote down. Before the sheet was stolen, Bessie recorded the sequence that satisfies for each Based on Bessie's information, help FJ restore the "lexicographically minimum" permutation that could have produced . A permutation is lexicographically smaller than a permutation if for some , for all and (in other words, the two permutations are identical up to a certain point, at which is smaller than ). It is guaranteed that at least one such exists.
输入格式
The first line of input contains a single integer The second line contains space-separated integers
输出格式
A single line with space-separated integers
数据范围
Test cases 2-4 satisfy Test cases 5-10 satisfy no additional constraints.
样例
样例 1
5
4 6 7 6
3 1 5 2 4
$a$ produces $b$ because $3+1=4$, $1+5=6$, $5+2=7$, and $2+4=6.$
Problem credits: Benjamin Qi and Chris Zhang