На самом деле, задачи 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]$$$, то одна из возможных последовательностей действий выглядит так:

Найдите лексикографически минимальную возможную последовательность элементов в деке после того, как будет обработана вся перестановка.

Последовательность $$$[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$$$).