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...
#incl
assistant
#Here is Python code to find the minimal possible number of inversions in the deque after the whole array is processed.
ude <bits/stdc++.h>
using namespace std;
template <class c>
struct rge {
  c b, e;
};
template <class c>
rge<c> range(c i, c j) {
  return rge<c>{i, j};
}
template <class c>
auto dud(c* x) -> decltype(cerr << *x, 0);
template <class c>
char dud(...);
struct debug {
  template <class c>
  debug& operator<<(const c&) {
    return *this;
  }
};
long long power(long long x, long long y, long long M) {
  long long res = 1;
  while (y > 0) {
    if (y & 1) res = (res * x) % M;
    y >>= 1;
    x = (x * x) % M;
  }
  return res % M;
}
long long power(long long x, long long y) {
  long long res = 1;
  while (y > 0) {
    if (y & 1) res = (res * x);
    y >>= 1;
    x = (x * x);
  }
  return res;
}
const long long mxn = 1e6 + 6, mod = 1e9 + 7, inf = 1e18;
long long t, casee = 1;
template <typename T>
class Segment_Tree {
 private:
  vector<T> arr;
  vector<T> seg_tree;
  long long N;
  long long def;

 public:
  Segment_Tree(vector<T> a, long long deff = 0) {
    N = a.size();
    def = deff;
    arr = a;
    seg_tree.resize(4 * N + 10, 0);
    build();
  }
  long long func(long long a, long long b) { return a + b; }
  void build() { build_it_for_me(0, N - 1, 1); }
  void build_it_for_me(long long lo, long long hi, long long pos) {
    assert(lo <= hi);
    if (lo == hi) {
      seg_tree[pos] = arr[lo];
      return;
    }
    long long mid = (lo + hi) / 2;
    build_it_for_me(lo, mid, 2 * pos);
    build_it_for_me(mid + 1, hi, 2 * pos + 1);
    seg_tree[pos] = func(seg_tree[2 * pos], seg_tree[2 * pos + 1]);
  }
  void update(long long ind, long long val) {
    update_it_for_me(ind, val, 0, N - 1, 1);
  }
  void update_it_for_me(long long ind, long long val, long long lo,
                        long long hi, long long pos) {
    if (lo == hi) {
      seg_tree[pos] = val;
      arr[ind] = val;
      return;
    }
    long long mid = (lo + hi) / 2;
    if (mid >= ind)
      update_it_for_me(ind, val, lo, mid, 2 * pos);
    else
      update_it_for_me(ind, val, mid + 1, hi, 2 * pos + 1);
    seg_tree[pos] =...