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...
 ... Write me a Python program to find the minimal possible number of inversions in the deque after the whole array is processed?
assistant
#Here is Python program to find the minimal possible number of inversions in the deque after the whole array is processed.

def naiveSolve():
    
    
    
    return


def solve():
    
    
    
    return

class SegmentTree():
    def __init__(self,arr,combinerFunction,isCommutative=True): # isCommutative means f(a,b)==f(b,a)
        self.n=len(arr)
        def cmb(a,b):
            if a==None: return b
            if b==None: return a
            return combinerFunction(a,b)
        self.cmb=cmb
        self.sz=self.n if isCommutative else pow(2,((self.n-1).bit_length())) # non-commutative needs power of 2 size
        self.t=[None]*(2*self.sz) # use None as initial value
        for i in range(self.n): self.t[i+self.sz]=arr[i]
        for i in range(self.sz-1,0,-1): self.pull(i)
    def pull(self,p):
        self.t[p]=self.cmb(self.t[2*p],self.t[2*p+1])
    def update(self,idx,val): # set val at idx
        idx+=self.sz
        self.t[idx]=val
        idx//=2
        while idx>0:
            self.pull(idx)
            idx//=2
    def query(self,l,r): # aggregated value in [l,r] inclusive
        l+=self.sz; r+=self.sz+1
        a=b=None
        while l<r:
            if l%2==1: a=self.cmb(a,self.t[l]); l+=1
            if r%2==1: r-=1; b=self.cmb(self.t[r],b)
            l//=2; r//=2
        return self.cmb(a,b)
def getMaxSegTree(arr):
    return SegmentTree(arr,lambda a,b:max(a,b),True)
def getMinSegTree(arr):
    return SegmentTree(arr,lambda a,b:min(a,b),True)
def getSumSegTree(arr):
    return SegmentTree(arr,lambda a,b:a+b,True)

def main():
    
    # notice that for each number added, the order of the prefix does not
    # its number of inversions. hence, just add to the side that creates
    # fewer inversions. use seg tree and coord compression
    
    t=int(input())
    allans=[]
    for _ in range(t):
        n=int(input())
        a=readIntArr()
        
        c=sorted(set(a))
        reverseMap={x:i for i,x in enumerate(c)}
        for i in range(n):
            a[i]=reverseMap[a[i]]
        
        maxN=max(a)+2
        st=getSumSegTree([0]*maxN)
        cnts=[0]*maxN
        ans=0
        for x in a:
   ...