D. Восстановить перестановку
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Последовательность целых чисел $$$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$$$ ($$$1 \le n \le 2 \cdot 10^{5}$$$) — размер перестановки.

Вторая строка содержит $$$n$$$ целых чисел $$$s_{1}, s_{2}, \ldots, s_{n}$$$ ($$$0 \le s_{i} \le \frac{n(n-1)}{2}$$$).

Гарантируется, что $$$s$$$ соответствует корректной перестановке длины $$$n$$$.

Выходные данные

Выведите $$$n$$$ целых чисел $$$p_{1}, p_{2}, \ldots, p_{n}$$$ — элементы восстановленной перестановки.

Можно показать, что ответ всегда уникальный.

Примеры
Входные данные
3
0 0 0
Выходные данные
3 2 1
Входные данные
2
0 1
Выходные данные
1 2
Входные данные
5
0 1 1 1 10
Выходные данные
1 4 3 2 5
Примечание

В первом примере для каждого $$$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$$$.