На самом деле, задачи E1 и E2 не имеют много общего. Вероятно, вам надо воспринимать их как две отдельные задачи.
Дана перестановка \(p\) размера \(n\). Перестановкой размера \(n\) называется массив размера \(n\), в котором каждое целое число от \(1\) до \(n\) встречается по одному разу. Например, \([1, 4, 3, 2]\) и \([4, 2, 1, 3]\) являются перестановками, а \([1, 2, 4]\) и \([1, 2, 2]\) — нет.
Рассмотрим пустой дек (двухстороннюю очередь). Дек — это структура данных, поддерживающая добавление элементов как в начало, так и в конец. Так, если сейчас в деке лежат элементы \([1, 5, 2]\), при добавлении элемента \(4\) в начало получится последовательность \([\color{red}{4}, 1, 5, 2]\), а при добавлении в конец — \([1, 5, 2, \color{red}{4}]\).
Элементы перестановки по очереди перемещаются в изначально пустой дек, начиная с \(p_1\) и заканчивая \(p_n\). Перед добавлением каждого элемента в дек разрешается выбрать, добавить его в начало или в конец.
Например, если рассмотреть перестановку \(p = [3, 1, 2, 4]\), то одна из возможных последовательностей действий выглядит так:
| \(\quad\) 1. | положить \(3\) в конец дека: | в деке лежит \([\color{red}{3}]\); |
| \(\quad\) 2. | положить \(1\) в начало дека: | в деке лежит \([\color{red}{1}, 3]\); |
| \(\quad\) 3. | положить \(2\) в конец дека: | в деке лежит \([1, 3, \color{red}{2}]\); |
| \(\quad\) 4. | положить \(4\) в конец дека: | в деке лежит \([1, 3, 2, \color{red}{4}]\); |
Найдите лексикографически минимальную возможную последовательность элементов в деке после того, как будет обработана вся перестановка.
Последовательность \([x_1, x_2, \ldots, x_n]\) лексикографически меньше последовательности \([y_1, y_2, \ldots, y_n]\), если существует такое \(i \leq n\), что \(x_1 = y_1\), \(x_2 = y_2\), \(\ldots\), \(x_{i - 1} = y_{i - 1}\) и \(x_i < y_i\). Иными словами, если последовательности \(x\) и \(y\) имеют некоторое (возможно, пустое) совпадающее начало, а следующий элемент последовательности \(x\) строго меньше соответствующего элемента последовательности \(y\). Например, последовательность \([1, 3, 2, 4]\) меньше последовательности \([1, 3, 4, 2]\), так как после совпадающего начала \([1, 3]\) в первой последовательности идет меньшее число (\(2\)), чем во второй (\(4\)).