22110번 - Обратная задача о наибольшей возрастающей подпоследовательности 스페셜 저지다국어

Обратные задачи часто встречаются в исследованиях по теоретической информатике. Обычно обратная задача формулируется так: по заданному решению требуется построить набор входных данных, на котором это решение достигается. В этой задаче вам требуется решить обратную задачу о наибольшей возрастающей подпоследовательности.

Напомним, что возрастающей подпоследовательностью последовательности a[1..n] длины n называют последовательность a[i₁] < a[i₂] < ...< a[i_k], где 1 ≤ i₁ < i₂ < ... < i_k ≤ n. Задача о наибольшей возрастающей подпоследовательности (НВП) заключается в том, чтобы найти возрастающую подпоследовательность заданной последовательности, имеющую максимальное число элементов.

При решение задачи о НВП, строится массив d[1..n], где d[i] — длина наибольшей возрастающей последовательности последовательности a[1..i], заканчивающейся на a[i].

Например, для последовательности a = [3, 2, 4, 1, 5, 6] построенный массив d имеет вид d = [1, 1, 2, 1, 3, 4].

Требуется по заданному массиву d найти такую последовательность a, такую что при решении задачи о НВП построенный массив d совпадает с заданным. Все числа в последовательности a должны быть различными целыми положительными и не превосходить 10¹⁵.

Первая строка содержит целое положительное число t — число тестовых примеров во входных данных. Далее следуют описания тестовых примеров.

Каждый тестовый пример описывается двумя строками. Первая строка содержит целое положительное число n — длину последовательности (1 ≤ n ≤ 300 000). Вторая строка содержит n целых положительных чисел — массив d.

Гарантируется, что сумма значений n по всем тестовым примерам не превышает 300 000.

Для каждого тестового примера выведите n различных целых положительных чисел, не превосходящих 10¹⁵ — искомую последовательность a. Гарантируется, что входные данные таковы, что искомая последовательность существует. Если возможных решений несколько, можно вывести любое.