У Стека есть массив \(a\) длины \(n\). У него также есть пустое множество \(S\). Заметим, что \(S\) не является мультимножеством.
Он выполнит следующую трехшаговую операцию ровно \(n\) раз:
- Выбрать индекс \(i\) такой, что \(1 \leq i \leq |a|\).
- Вставить\(^\dagger\) \(a_i + i\) в \(S\).
- Удалить \(a_i\) из \(a\). Обратите внимание, что индексы всех элементов справа от \(a_i\) уменьшаются на \(1\).
Обратите внимание, что после \(n\) операций массив \(a\) станет пустым.
После Стек построит новый массив \(b\), который является \(S\), отсортированным в порядке убывания. Формально, \(b\) — это массив длины \(|S|\), где \(b_i\) — \(i\)-й наибольший элемент \(S\) для всех \(1 \leq i \leq |S|\).
Найдите лексикографически наибольший\(^\ddagger\) массив \(b\), который может получить Стек.
\(^\dagger\) Множество может содержать только уникальные элементы. Вставка элемента, который уже присутствует в множестве, не изменит множество.
\(^\ddagger\) Массив \(p\) лексикографически больше массива \(q\) тогда и только тогда, когда выполняется одно из следующих условий:
- \(q\) является префиксом \(p\), но \(p \ne q\); или
- в первой позиции, где \(p\) и \(q\) различаются, массив \(p\) имеет больший элемент, чем соответствующий элемент в \(q\).
Заметим, что \([3,1,4,1,5]\) лексикографически больше, чем \([3,1,3]\), \([\,]\) и \([3,1,4,1]\), но не больше \([3,1,4,1,5,9]\), \([3,1,4,1,5]\) и \([4]\).
Примечание
В первом наборе входных данных выберите \(i=1\) в первой операции, вставьте \(a_1 + 1 = 3\) в \(S\) и удалите \(a_1\) из \(a\). После первой операции массив \(a\) станет \(a=[1]\). Во второй операции снова выберите \(i=1\) и вставьте \(a_1 + 1 = 2\) в \(S\). Таким образом, \(S=\{2, 3\}\), и \(b = [3, 2]\).
Обратите внимание, что если в первой операции выбрать \(i=2\), а во второй выбрать \(i=1\), то \(S=\{3\}\), так как \(3\) будет вставлено дважды, в результате чего \(b=[3]\).
Поскольку \([3,2]\) лексикографически больше \([3]\), то в первой операции следует выбрать \(i=1\).
Во втором примере в каждой операции нужно выбирать последний элемент.