Сета придумывает задачи для CCO! Она придумала следующую задачу:
Дан массив $A[1, \dots, N]$, значения которого находятся в диапазоне $[1, N]$. Определим $B[i]$ как количество пар $(\ell, r)$ таких, что $\ell \le i \le r$ и $$A[i] = \min(A[\ell], A[\ell+1], \dots, A[r-1], A[r]).$$ Выведите массив $B[1, \dots, N]$.
Однако за день до CCO компьютер Сеты сломался, и она смогла восстановить только выходные файлы. Зная выходной массив $B[1, \dots, N]$, можете ли вы написать программу для восстановления входного массива $A[1, \dots, N]$?
Сета напоминает, что массив $A$ не обязательно уникален, и она примет любой подходящий массив.
Входные данные
В первой строке входных данных содержится единственное целое число $N$. Во второй строке содержатся $N$ целых чисел $B[1], \dots, B[N]$, разделенных пробелами ($1 \le B[i] \le N^2$).
В следующей таблице показано распределение 25 баллов:
| Баллы | Ограничения на $N$ | Дополнительные условия |
|---|---|---|
| 2 балла | $1 \le N \le 8$ | Нет. |
| 3 балла | $1 \le N \le 5\,000$ | Исходный массив $A$ является перестановкой. |
| 5 баллов | $1 \le N \le 3 \times 10^5$ | Исходный массив $A$ является перестановкой. |
| 5 баллов | $1 \le N \le 3 \times 10^5$ | Нет. |
| 5 баллов | $1 \le N \le 5 \times 10^6$ | Исходный массив $A$ является перестановкой. |
| 5 баллов | $1 \le N \le 5 \times 10^6$ | Нет. |
Выходные данные
Выведите $N$ целых чисел, разделенных пробелами — массив $A[1], \dots, A[N]$, где $1 \le A[i] \le N$. Гарантируется, что всегда существует хотя бы один подходящий массив $A$.
Если существует более одного подходящего массива, вы можете вывести любой из них. В частности, даже если исходный массив $A$ был перестановкой, ваш ответ не обязан быть перестановкой.
Примеры
Пример 1
3 3 1 2
Выходные данные 1
1 3 2
Примечание
- Подмассивы $[1, 3, 2]$, $[1, 3]$, $[1]$ имеют минимум $1$. Всего таких подмассивов $3$.
- Подмассив $[3]$ имеет минимум $3$. Всего такой подмассив $1$.
- Подмассивы $[3, 2]$ и $[2]$ имеют минимум $2$. Всего таких подмассивов $2$.
Пример 2
2 2 2
Выходные данные 2
1 1
Пример 3
3 1 4 1
Выходные данные 3
2 1 3
Примечание
Заметьте, что массив $A = [2, 1, 2]$ также был бы принят проверяющей системой.