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...
impor ... Give me a Python code to find the minimal possible number of inversions in the deque after the whole array is processed?
assistant
#Here is Python code to find the minimal possible number of inversions in the deque after the whole array is processed.
t sys
readline=sys.stdin.readline
from collections import deque
class Segment_Tree:
    def __init__(self,N,f,e,lst=None):
        self.f=f
        self.e=e
        self.N=N
        if lst==None:
            self.segment_tree=[self.e]*2*self.N
        else:
            assert len(lst)<=self.N
            self.segment_tree=[self.e]*self.N+[x for x in lst]+[self.e]*(N-len(lst))
            for i in range(self.N-1,0,-1):
                self.segment_tree[i]=self.f(self.segment_tree[i<<1],self.segment_tree[i<<1|1])

    def __getitem__(self,i):
        if type(i)==int:
            if -self.N<=i<0:
                return self.segment_tree[i+self.N*2]
            elif 0<=i<self.N:
                return self.segment_tree[i+self.N]
            else:
                raise IndexError('list index out of range')
        else:
            a,b,c=i.start,i.stop,i.step
            if a==None or a<-self.N:
                a=self.N
            elif self.N<=a:
                a=self.N*2
            elif a<0:
                a+=self.N*2
            else:
                a+=self.N
            if b==None or self.N<=b:
                b=self.N*2
            elif b<-self.N:
                b=self.N
            elif b<0:
                b+=self.N*2
            else:
                b+=self.N
            return self.segment_tree[slice(a,b,c)]

    def __setitem__(self,i,x):
        if -self.N<=i<0:
            i+=self.N*2
        elif 0<=i<self.N:
            i+=self.N
        else:
            raise IndexError('list index out of range')
        self.segment_tree[i]=x
        while i>1:
            i>>= 1
            self.segment_tree[i]=self.f(self.segment_tree[i<<1],self.segment_tree[i<<1|1])

    def Build(self,lst):
        for i,x in enumerate(lst,self.N):
            self.segment_tree[i]=x
        for i in range(self.N-1,0,-1):
            self.segment_tree[i]=self.f(self.segment_tree[i<<1],self.segment_tree[i<<1|1])

    def Fold(self,L=None,R=None):
        if L==None or L<-self.N:
            L=self.N
        elif...