На самом деле, задачи E1 и E2 не имеют много общего. Вероятно, вам надо воспринимать их как две отдельные задачи.
Дан массив целых чисел \(a[1 \ldots n] = [a_1, a_2, \ldots, a_n]\).
Рассмотрим пустой дек (двухстороннюю очередь). Дек — это структура данных, поддерживающая добавление элементов как в начало, так и в конец. Так, если сейчас в деке лежат элементы \([3, 4, 4]\), при добавлении элемента \(1\) в начало получится последовательность \([\color{red}{1}, 3, 4, 4]\), а при добавлении в конец — \([3, 4, 4, \color{red}{1}]\).
Элементы массива по очереди перемещаются в изначально пустой дек, начиная с \(a_1\) и заканчивая \(a_n\). Перед добавлением каждого элемента в дек разрешается выбрать, добавить его в начало или в конец.
Например, если рассмотреть массив \(a = [3, 7, 5, 5]\), то одна из возможных последовательностей действий выглядит так:
| \(\quad\) 1. | положить \(3\) в начало дека: | в деке лежит \([\color{red}{3}]\); |
| \(\quad\) 2. | положить \(7\) в конец дека: | в деке лежит \([3, \color{red}{7}]\); |
| \(\quad\) 3. | положить \(5\) в конец дека: | в деке лежит \([3, 7, \color{red}{5}]\); |
| \(\quad\) 4. | положить \(5\) в начало дека: | в деке лежит \([\color{red}{5}, 3, 7, 5]\); |
Определите, какое минимальное число инверсий может быть в деке после того, как будет обработан весь массив.
Инверсией в последовательности \(d\) называется пара индексов \((i, j)\) такая, что \(i < j\) и \(d_i > d_j\). Например, в массиве \(d = [5, 3, 7, 5]\) ровно две инверсии — \((1, 2)\) и \((3, 4)\), так как \(d_1 = 5 > 3 = d_2\) и \(d_3 = 7 > 5 = d_4\).
Выходные данные
Выведите \(t\) строк, каждая из которых содержит ответ на соответствующий набор входных данных. В качестве ответа выведите одно целое число — минимальное возможное количество инверсий, которое может быть в последовательности, находящейся в деке, после выполнения описанного алгоритма.
Примечание
Один из способов получить в деке из последовательности \([3, 7, 5, 5]\) (первый набор входных данных из примера) последовательность \([5, 3, 7, 5]\), содержащую только две инверсии, описан в условии задачи.
Также в этом примере можно было получить две инверсии, просто положив каждый элемент исходного массива в конец дека. В таком случае в деке будет лежать исходная последовательность \([3, 7, 5, 5]\), также содержащая ровно две инверсии.