Написать программу на Pascal либо на C++

Обратные задачи часто встречаются в исследованиях по теоретической информатике. Обычно обратная задача формулируется так: по заданному решению требуется построить набор входных данных, на котором это решение достигается. В этой задаче вам требуется решить обратную задачу о наибольшей возрастающей подпоследовательности. Напомним, что возрастающей подпоследовательностью последовательности a[1..n] длины n называют последовательность a[i1] < a[i2] < ...< a[ik], где 1 ? i1 < i2 < ... < ik ? 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^15. Формат входных данных: Первая строка содержит целое положительное число t — число тестовых примеров во входных данных. Далее следуют описания тестовых примеров. Каждый тестовый пример описывается двумя строками. Первая строка содержит целое положительное число n — длину последовательности (1 ? n ? 300 000). Вторая строка содержит n целых положительных чисел — массив d. Гарантируется, что сумма значений n по всем тестовым примерам не превышает 300 000. Формат выходных данных: Для каждого тестового примера выведите n различных целых положительных чисел, не превосходящих 1015 — искомую последовательность a. Гарантируется, что входные данные таковы, что искомая последовательность существует. Если возможных решений несколько, можно вывести любое. Примеры: Входные данные 2 5 1 2 2 1 3 8 1 2 3 1 4 2 3 5 Выходные данные 2 5 3 1 4 4 6 8 1 9 2 7 10