E2. Оптимизация массива деком
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

На самом деле, задачи 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$$$ ($$$1 \leq t \leq 1000$$$) — количество наборов входных данных.

В следующих $$$2t$$$ строках даны описания наборов входных данных.

В описании каждого набора входных данных первая строка содержит целое число $$$n$$$ ($$$1 \le n \le 2 \cdot 10^5$$$) — размер массива, а во второй строке через пробел перечислены $$$n$$$ целых чисел $$$a_i$$$ ($$$-10^9 \le a_i \le 10^9$$$) — элементы массива.

Гарантируется, что сумма $$$n$$$ по всем наборам входных данных не превосходит $$$2 \cdot 10^5$$$.

Выходные данные

Выведите $$$t$$$ строк, каждая из которых содержит ответ на соответствующий набор входных данных. В качестве ответа выведите одно целое число — минимальное возможное количество инверсий, которое может быть в последовательности, находящейся в деке, после выполнения описанного алгоритма.

Пример
Входные данные
6
4
3 7 5 5
3
3 2 1
3
3 1 2
4
-1 2 2 -1
4
4 5 1 3
5
1 3 1 3 2
Выходные данные
2
0
1
0
1
2
Примечание

Один из способов получить в деке из последовательности $$$[3, 7, 5, 5]$$$ (первый набор входных данных из примера) последовательность $$$[5, 3, 7, 5]$$$, содержащую только две инверсии, описан в условии задачи.

Также в этом примере можно было получить две инверсии, просто положив каждый элемент исходного массива в конец дека. В таком случае в деке будет лежать исходная последовательность $$$[3, 7, 5, 5]$$$, также содержащая ровно две инверсии.