У фермера Джона есть перестановка \(p_1, p_2, \ldots, p_n\), в которой каждое целое число от \(0\) до \(n-1\) встречается ровно один раз. Он дает Бесси массив \(a\) длины \(n\) и просит ее восстановить \(p\) на основе \(a\).
Массив \(a\) строится так: \(a_i\) = \(\texttt{MEX}(p_1, p_2, \ldots, p_i) - p_i\), где \(\texttt{MEX}\) массива — это минимальное целое неотрицательное число, которое не встречается в этом массиве. Например, \(\texttt{MEX}(1, 2, 3) = 0\), а \(\texttt{MEX}(3, 1, 0) = 2\).
Помогите Бесси построить любую перестановку \(p\), удовлетворяющую массиву \(a\). Гарантируется, что вам даются входные данные, для которых существует хотя бы одна допустимая перестановка \(p\). Если существует несколько возможных \(p\), вы можете вывести любую из них.
Выходные данные
Для каждого набора входных данных выведите на отдельной строке \(n\) целых чисел, являющихся элементами \(p\).
Если существует несколько решений, выведите любое из них.
Примечание
В первом наборе входных данных \(p = [0, 1, 4, 2, 3]\) является одним из возможных ответов.
Для этой перестановки \(a\) будет вычисляться так: \(a_1 = \texttt{MEX}(0) - 0 = 1\), \(a_2 = \texttt{MEX}(0, 1) - 1 = 1\), \(a_3 = \texttt{MEX}(0, 1, 4) - 4 = -2\), \(a_4 = \texttt{MEX}(0, 1, 4, 2) - 2 = 1\), \(a_5 = \texttt{MEX}(0, 1, 4, 2, 3) - 3 = 2\).
Таким образом, как и требовалось, \(a\) будет равняться \([1, 1, -2, 1, 2]\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
3
5
1 1 -2 1 2
5
1 1 1 1 1
3
-2 1 2
|
0 1 4 2 3
0 1 2 3 4
2 0 1
|