human
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 … n] = [a_1, a_2, …, 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:    1. |  add 3 to the beginning of the deque: |  deque has a sequence [\color{red}{3}] in it.
  
---|---|---  
  2. |  add 7 to the end of the deque: |  deque has a sequence [3, \color{red}{7}] in it.
  
  3. |  add 5 to the end of the deque: |  deque has a sequence [3, 7, \color{red}{5}] in it.
  
  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.

Input

The first line contains an integer t (1 ≤ t ≤ 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 ≤ n ≤ 2 ⋅ 10^5) — array size. The second line of the description contains n space-separated integers a_i (-10^9 ≤ a_i ≤ 10^9) — elements of the array.

It is...
assistant
#Here is Python code to find the minimal possible number of inversions in the deque after the whole array is processed.

from sys import stdin
input = stdin.readline

 
class segtree:
 
    def __init__(self , n):
 
        self.st = [0]*(4 * n)
 
        self.size = n - 1 
 
    def update(self , ind , value):
 
        l , h = 0 , self.size
 
        i = 0
        while(l < h):
 
            mid = (l + h)//2
 
            if(ind > mid):
                l = mid + 1
                i = 2*i + 2
            else:
                i = 2*i + 1
                h = mid
 
        self.st[i] += value
 
        while(i > 0):
   
            i = (i - 1)//2
            self.st[i] = self.st[2*i + 1] + self.st[2*i + 2]
        
 
 
    def query(self , x , y ,l = 0 , h = -1 , i = 0):
        if(h == -1):
            h = self.size
 
        if(l >= x and h <= y):return self.st[i]
 
        if(l > y or h < x):return 0
   
        mid = (l + h)//2
 
        left = self.query(x , y ,l , mid , 2*i + 1)
        right = self.query(x,  y , mid + 1 , h , 2*i + 2)
 
        return left + right



def answer():

    x = [[a[i] , i] for i in range(n)]
    x.sort()
    
    st = segtree(n)

    ans , prev = 0 , 1e10
    for i in range(n):

        if(prev == x[i][0]):same += 1
        else:
            prev = x[i][0]
            same = 0

        less = st.query(0 , x[i][1]) - same
        greater = x[i][1] - less - same

        ans += min(less , greater)

        st.update(x[i][1] , 1)
        
    return ans

 
 
for T in range(int(input())):

    n = int(input())
    a = list(map(int,input().split()))
 
    print(answer())