Перестановка \(p\) — это последовательность целых чисел \(p=[p_1, p_2, \dots, p_n]\), которая состоит из \(n\) различных положительных целых чисел от \(1\) до \(n\). Например, следующие последовательности являются перестановками — \([3, 4, 1, 2]\), \([1]\), \([1, 2]\). Следующие последовательности не являются перестановками — \([0]\), \([1, 2, 1]\), \([2, 3]\), \([0, 1, 2]\).
Важный ключ спрятан в закрытой коробке, которую вам нужно открыть. Чтобы открыть коробку вам нужно ввести секретный ключ. Секретный ключ это перестановка \(p\) длины \(n\).
Эту перестановку вы не знаете, вы знаете только массив \(q\) префиксных максимумов этой перестановки. Формально:
- \(q_1=p_1\),
- \(q_2=\max(p_1, p_2)\),
- \(q_3=\max(p_1, p_2,p_3)\),
- ...
- \(q_n=\max(p_1, p_2,\dots,p_n)\).
Вы хотите построить любую возможную исходную перестановку, которая согласуется с заданным массивом. Другими словами, найдите любую перестановку, что \(q\) для этой перестановки равен данному массиву.
Примечание
В первом наборе входных данных примера \([1,3,4,5,2]\) это единственный возможный ответ.
- \(q_{1} = p_{1} = 1\);
- \(q_{2} = \max(p_{1}, p_{2}) = 3\);
- \(q_{3} = \max(p_{1}, p_{2}, p_{3}) = 4\);
- \(q_{4} = \max(p_{1}, p_{2}, p_{3}, p_{4}) = 5\);
- \(q_{5} = \max(p_{1}, p_{2}, p_{3}, p_{4}, p_{5}) = 5\).
Можно доказать, что для второго набора входных данных примера не существует ответа.