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 program to find the minimal possible number of inversions in the deque after the whole array is processed.

Q = int(input())
#BIT(Fenwick Tree)

class BIT: 
  def __init__(self, n, op=lambda x,y: x+y, inv=lambda x:-x, ie = 0):
    self.n = n
    self.op = op
    self.ie = ie
    self.inv = inv
    self.el = [ie]*(n+1) 
    self.data = [ie]*(n+1)
  
  def add(self, i, x):
    op = self.op
    self.el[i] = op(self.el[i], x)
    data = self.data
    while i <= self.n:
      data[i] = op(data[i], x)
      i += i & -i
      
  def _obtain(self, i): # sum from 1 to i
    data = self.data
    op = self.op
    ans = 0
    while i > 0:
      ans = op(data[i], ans)
      i -= i & -i
    return ans
    
  def apply(self, l, r):
    return  self.op(self.inv(self._obtain(l-1)), self._obtain(r-1))
      
  def construct(self, A):
    for i, x in enumerate(A):
      self.add(i+1,x)     

from collections import defaultdict as dft
def main():
  N = int(input())
  A = list(map(int,input().split()))
  
  A_set = set(A)
  A_list = list(A_set)
  A_list.sort()
  A_inv = dft(int)
  for i, a in enumerate(A_list):
    A_inv[a] = i + 1
  M = len(A_inv)
  bt = BIT(M)
  
  ans = 0
  for a in A:
    a_id = A_inv[a]
    inv_l = bt.apply(1, a_id)
    inv_r = bt.apply(a_id+1, M+1)
    ans += min(inv_l, inv_r)
    
    bt.add(a_id, 1)
    
  print(ans)
    
    
"""
import bisect
def main():
  N = int(input())
  A = list(map(int,input().split()))
  
  ans = []
  for i in range(1,N):
    if A[i-1] < A[i]: continue
    
    j = bisect.bisect(A[:i], A[i])
    ans.append([j+1, i+1, i - j])
    a_i = A[i]
    for i2 in range(i-1, j-1, -1):
      A[i2+1] = A[i2]
    A[j] = a_i
  #print(A)
  print(len(ans))
  if len(ans) > 0:
    for a in ans:
      print(*a)
  else:
    print(*[])

def judge(A, K):
  S = [[0 for _ in range(W)] for _ in range(H)]
  
  
  
def main():
  N, M, K = map(int,input().split())
  H = M + N + 1
  W = M + N + 1
  A = [[0 for _ in range(W)] for _ in range(H)]
  At = [[0 for _ in range(H)] for _ in range(W)]
  
  S = [input() for _ in range(N)]
  for i in range(N):
    for j in range(M):
      if S[i][j] == ".":
       ...