Последовательность целых чисел \(p_{1},p_{2}, \ldots,p_{n}\) называется перестановкой, если она содержит каждое число от \(1\) до \(n\) ровно один раз. Например, следующие последовательности перестановки: \([3,1,2], [1], [1,2,3,4,5]\) и \([4,3,1,2]\). А следующие последовательности не являются перестановками: \([2], [1,1], [2,3,4]\).
Загадана перестановка длины \(n\).
Для каждого индекса \(i\) вам дано \(s_{i}\), равное сумме всех таких \(p_{j}\), что \(j < i\) и \(p_{j} < p_{i}\). Иначе говоря, \(s_i\) — это сумма всех элементов до \(i\)-го элемента, которые меньше \(i\)-го элемента.
Ваша задача — восстановить перестановку.
Выходные данные
Выведите \(n\) целых чисел \(p_{1}, p_{2}, \ldots, p_{n}\) — элементы восстановленной перестановки.
Можно показать, что ответ всегда уникальный.
Примечание
В первом примере для каждого \(i\) не существует позиции \(j\), удовлетворяющей обоим условиям, соответственно \(s_i\) всегда равен \(0\).
Во втором примере для \(i = 2\) позиция \(j = 1\) удовлетворяет условиям, так что \(s_2 = p_1\).
В третьем примере для \(i = 2, 3, 4\) только позиция \(j = 1\) удовлетворяет условиям, так что \(s_2 = s_3 = s_4 = 1\). Для \(i = 5\) возможны все позиции \(j = 1, 2, 3, 4\), и \(s_5 = p_1 + p_2 + p_3 + p_4 = 10\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
3
0 0 0
|
3 2 1
|
|
2
|
2
0 1
|
1 2
|
|
3
|
5
0 1 1 1 10
|
1 4 3 2 5
|