CF1579E2.Array Optimization by Deque

In fact, the problems E1 and E2 do not have much in common. You should probably think of them as two separate problems.

You are given an integer array $a[1 \ldots n] = [a_1, a_2, \ldots, a_n]$.

Let us consider an empty deque (double-ended queue). A deque is a data structure that supports adding elements to both the beginning and the end. So, if there are elements $[3, 4, 4]$ currently in the deque, adding an element $1$ to the beginning will produce the sequence $[\color{red}{1}, 3, 4, 4]$, and adding the same element to the end will produce $[3, 4, 4, \color{red}{1}]$.

The elements of the array are sequentially added to the initially empty deque, starting with $a_1$ and finishing with $a_n$. Before adding each element to the deque, you may choose whether to add it to the beginning or to the end.

For example, if we consider an array $a = [3, 7, 5, 5]$, one of the possible sequences of actions looks like this:

$\quad$ 1.

add $3$ to the beginning of the deque:

deque has a sequence $[\color{red}{3}]$ in it;

$\quad$ 2.

add $7$ to the end of the deque:

deque has a sequence $[3, \color{red}{7}]$ in it;

$\quad$ 3.

add $5$ to the end of the deque:

deque has a sequence $[3, 7, \color{red}{5}]$ in it;

$\quad$ 4.

add $5$ to the beginning of the deque:

deque has a sequence $[\color{red}{5}, 3, 7, 5]$ in it;

Find the minimal possible number of inversions in the deque after the whole array is processed.

An inversion in sequence $d$ is a pair of indices $(i, j)$ such that $i \lt j$ and $d_i \gt d_j$. For example, the array $d = [5, 3, 7, 5]$ has exactly two inversions — $(1, 2)$ and $(3, 4)$, since $d_1 = 5 \gt 3 = d_2$ and $d_3 = 7 \gt 5 = d_4$.

事实上，题目 E1 和 E2 并没有太多共同之处。你应当将它们视为两个独立的问题。

给定一个整数数组 $a[1 \ldots n] = [a_1, a_2, \ldots, a_n]$。

考虑一个初始为空的双端队列（deque）。双端队列是一种支持在开头和末尾均插入元素的数据结构。例如，若当前双端队列中已有元素 $[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 \lt j$ 且 $d_i \gt d_j$。例如，数组 $d = [5, 3, 7, 5]$ 恰好包含两个逆序对 —— $(1, 2)$ 和 $(3, 4)$，因为 $d_1 = 5 \gt 3 = d_2$，且 $d_3 = 7 \gt 5 = d_4$。

The first line contains an integer $t$ ($1 \leq t \leq 1000$) — the number of test cases.

The next $2t$ lines contain descriptions of the test cases.

The first line of each test case description contains an integer $n$ ($1 \le n \le 2 \cdot 10^5$) — array size. The second line of the description contains $n$ space-separated integers $a_i$ ($-10^9 \le a_i \le 10^9$) — elements of the array.

It is guaranteed that the sum of $n$ over all test cases does not exceed $2 \cdot 10^5$.

第一行包含一个整数 $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$。

Print $t$ lines, each line containing the answer to the corresponding test case. The answer to a test case should be a single integer — the minimal possible number of inversions in the deque after executing the described algorithm.

输出 $t$ 行，每行包含对应测试用例的答案。每个测试用例的答案应为一个整数——即执行所述算法后双端队列中逆序对的最小可能数量。

One of the ways to get the sequence $[5, 3, 7, 5]$ in the deque, containing only two inversions, from the initial array $[3, 7, 5, 5]$ (the first sample test case) is described in the problem statement.

Also, in this example, you could get the answer of two inversions by simply putting each element of the original array at the end of the deque. In this case, the original sequence $[3, 7, 5, 5]$, also containing exactly two inversions, will be in the deque as-is.

从初始数组 $[3, 7, 5, 5]$（第一个样例测试用例）出发，得到双端队列中序列 $[5, 3, 7, 5]$（恰好包含两个逆序对）的一种方法已在题目陈述中描述。

此外，在该示例中，你也可以简单地将原数组的每个元素依次添加至双端队列尾部，从而得到两个逆序对的答案。此时，原序列 $[3, 7, 5, 5]$（也恰好包含两个逆序对）将原封不动地保留在双端队列中。