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...
Solve the task in PYTHON3.

=====
What is 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.

'''
Array Optimization by Deque
'''

class OsTree:
    def __init__(self, max_val=10**6):
        self.N = max_val
        self.tree = [0]*(self.N+1)  # tree[i] = count nodes with val i
        self.size = 0               # count inserted numbers

    def _cumsum(self, i):  # sum tree[1..i]
        s = 0
        while i > 0:
            s += self.tree[i]
            i -= i & (-i)  # 110 -> 100
        return s

    def _add(self, i, val):  # add val to tree[i] (1-based)
        while i <= self.N:
            self.tree[i] += val
            i += i & (-i)  # 101 -> 110
    
    def insert(self, val):  # increment count of val 
        self._add(val, 1)
        self.size += 1
    
    def get_rank(self, val):  # how many numbers <= val
        return self._cumsum(val)

def solve(nums, N):
    val2idx = {v:i+1 for i,v in enumerate(sorted(list(set(nums))))}  # num -> sorted idx
    tree = OsTree(2*10**5)
    res = 0
    for num in nums:
        idx = val2idx[num] 
        smaller = tree.get_rank(idx-1)          # count strictly smaller
        bigger = tree.size - tree.get_rank(idx) # count strictly bigger
        res += min(smaller, bigger)
        tree.insert(idx)
    return res
 

def main():
    from sys import stdin
    
    T = int(stdin.readline().strip())
    for _ in range(T):
        N = int(stdin.readline().strip())
        nums = list(map(int, stdin.readline().strip().split()))
        out = solve(nums, N)
        print(out)

def test():
    from random import randint
    N = 2*10**5

    nums_rand = [randint(-10**9, 10**9) for _ in range(N)]
    nums_eq = [10**9]*N
    nums_inc = list(range(N))
    nums_dec = list(range(N))[::-1]

    for nums in [nums_rand, nums_eq, nums_inc, nums_dec]:
        out = solve(nums, N)
        print(out)

if __name__ == '__main__':
    main()
    # test()