Array Optimization by Deque

题意翻译

给你一个序列 $a$ 和一个双端队列。 你需要**按顺序**操作 $a_i$ ，具体地，每一次操作是把 $a_i$ 从双端队列的队头或者队尾入队。 求把 $a$ 中所有的元素都入队之后，双端队列中逆序对数量的最小值。 测试包含多组数据，对于每一组数据，输出一个数，表示你的答案。

题目描述

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](https://tinyurl.com/pfeucbux) (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 < j $ and $ d_i > d_j $ . For example, the array $ d = [5, 3, 7, 5] $ has exactly two inversions — $ (1, 2) $ and $ (3, 4) $ , since $ d_1 = 5 > 3 = d_2 $ and $ d_3 = 7 > 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 $ .

输出格式

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.

输入输出样例

输入样例 #1

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

输出样例 #1

2
0
1
0
1
2

说明

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.

题意翻译

给你一个序列 $a$ 和一个双端队列。 你需要**按顺序**操作 $a_i$ ，具体地，每一次操作是把 $a_i$ 从双端队列的队头或者队尾入队。 求把 $a$ 中所有的元素都入队之后，双端队列中逆序对数量的最小值。 测试包含多组数据，对于每一组数据，输出一个数，表示你的答案。