Последовательность из \(n\) чисел называется перестановкой, если она содержит в себе все числа от \(1\) до \(n\) ровно по одному разу. Например, последовательности [\(3, 1, 4, 2\)], [\(1\)] и [\(2,1\)] являются перестановками, а [\(1,2,1\)], [\(0,1\)] и [\(1,3,4\)] — нет.
Для перестановки \(p\) чётной длины \(n\) можно получить массив \(b\) длины \(\frac{n}{2}\) такой, что:
- \(b_i = \max(p_{2i - 1}, p_{2i})\) для \(1 \le i \le \frac{n}{2}\)
Например, если \(p\) = [\(2, 4, 3, 1, 5, 6\)], то:
- \(b_1 = \max(p_1, p_2) = \max(2, 4) = 4\)
- \(b_2 = \max(p_3, p_4) = \max(3,1)=3\)
- \(b_3 = \max(p_5, p_6) = \max(5,6) = 6\)
Итого получим
\(b\) =
\([4, 3, 6]\).
Для заданного массива \(b\) найдите лексикографически минимальную перестановку \(p\) такую, что из неё можно получить заданный массив \(b\).
Если \(b\) = [\(4,3,6\)], то лексикографически минимальная перестановка, из которой можно его получить, это \(p\) = [\(1,4,2,3,5,6\)], так как:
- \(b_1 = \max(p_1, p_2) = \max(1, 4) = 4\)
- \(b_2 = \max(p_3, p_4) = \max(2, 3) = 3\)
- \(b_3 = \max(p_5, p_6) = \max(5, 6) = 6\)
Перестановка \(x_1, x_2, \dots, x_n\) лексикографически меньше перестановки \(y_1, y_2 \dots, y_n\), если и только если существует такое \(i\) (\(1 \le i \le n\)), что \(x_1=y_1, x_2=y_2, \dots, x_{i-1}=y_{i-1}\) и \(x_i<y_i\).