description: 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 guaranteed that the sum of n over all test cases does not exceed 2 ⋅ 10^5.
  
  Output
  
  Print t lines, each line containing the answer to the corresponding test case. The answer to a test case should be a single integer — the minimal possible number of inversions in the deque after executing the described algorithm.
  
  Example
  
  Input
  
  
  6
  4
  3 7 5 5
  3
  3 2 1
  3
  3 1 2
  4
  -1 2 2 -1
  4
  4 5 1 3
  5
  1 3 1 3 2
  
  
  Output
  
  
  2
  0
  1
  0
  1
  2
  
  Note
  
  One of the ways to get the sequence [5, 3, 7, 5] in the deque, containing only two inversions, from the initial array [3, 7, 5, 5] (the first sample test case) is described in the problem statement. 
  
  Also, in this example, you could get the answer of two inversions by simply putting each element of the original array at the end of the deque. In this case, the original sequence [3, 7, 5, 5], also containing exactly two inversions, will be in the deque as-is.
solution: import java.util.*;
  import java.io.*;
  
  public class Omar {
  	static Scanner sc = new Scanner(System.in);
  	static PrintWriter pw = new PrintWriter(System.out);
  
  	public static void main(String[] args) throws IOException, InterruptedException {
  		int t = sc.nextInt();
  		while (t-- > 0) {
  			int n = sc.nextInt();
  			Integer[] arr = sc.nextIntegerArray(n);
  			Integer[] temp = arr.clone();
  			Arrays.sort(temp);
  			HashMap<Integer, Integer> hm = new HashMap<>();
  			for (int i = 0; i < n; i++)
  				if (!hm.containsKey(temp[i]))
  					hm.put(temp[i], i);
  			SegmentTree sg = new SegmentTree(n);
  			long ans = 0;
  			for (Integer i : arr) {
  				int ind = hm.get(i);
  				long before = ind == 0 ? 0 : sg.query(1, ind);
  				long after = ind == n - 1 ? 0 : sg.query(ind + 2, n);
  				ans+=Math.min(after, before);
  				sg.updatePoint(ind+1, 1);
  			}
  			pw.println(ans);
  		}
  
  		pw.flush();
  	}
  
  	static class SegmentTree {
  		int[] sTree, arr;
  		int N;
  
  		public SegmentTree(int n) {
  			N = 1;
  			while(N<n)
  				N<<=1;
  			sTree = new int[N << 1];
  		}
  
  		public void updatePoint(int idx, int value) {
  			idx += N - 1;
  			sTree[idx] += value;
  			idx = idx >> 1;
  			while (idx > 0) {
  				int left = idx << 1;
  				int right = idx << 1 | 1;
  				sTree[idx] = sTree[left] + sTree[right];
  				idx >>= 1;
  			}
  		}
  
  		public long query(int i, int j) {
  			return query(1, 1, N, i, j);
  		}
  
  		public long query(int node, int l, int r, int i, int j) {
  			if (i <= l && r <= j) {
  				return sTree[node];
  			}
  			if (r < i || l > j) {
  				return 0;
  			}
  			int leftChild = node << 1;
  			int rightChild = node << 1 | 1;
  			int mid = l + r >> 1;
  			long leftQ = query(leftChild, l, mid, i, j);
  			long rightQ = query(rightChild, mid + 1, r, i, j);
  			return leftQ + rightQ;
  		}
  
  	}
  
  	static class pair {
  		long x;
  		long y;
  
  		public pair(long a, long b) {
  			this.x = a;
  			this.y = b;
  		}
  
  		public void swap(pair p) {
  			pair temp = new pair(p.x, p.y);
  			p.x = this.x;
  			p.y = this.y;
  			this.x = temp.x;
  			this.y = temp.y;
  		}
  
  		public String toString() {
  			return x + "," + y + " ";
  		}
  
  		public boolean equals(pair p) {
  			if (x == p.x && y == p.y)
  				return true;
  			return false;
  		}
  	}
  
  	static class four {
  		long ans, pre, suf, tot;
  
  		public four(long w, long x, long y, long z) {
  			ans = w;
  			pre = x;
  			suf = y;
  			tot = z;
  		}
  
  		public String toString() {
  			return ans + " " + pre + " " + suf + " " + tot + "     ";
  		}
  	}
  
  	static class UnionFind {
  		int[] p, rank, setSize;
  		int numSets;
  
  		public UnionFind(int N) {
  			numSets = N;
  			p = new int[N + 1];
  			rank = new int[N + 1];
  			setSize = new int[N + 1];
  			for (int i = 0; i <= N; i++) {
  				p[i] = i;
  				setSize[i] = 1;
  			}
  		}
  
  		public int findSet(int i) {
  			return p[i] == i ? i : (p[i] = findSet(p[i]));
  		}
  
  		public boolean isSameSet(int i, int j) {
  			return findSet(i) == findSet(j);
  		}
  
  		public void join(int i, int j) {
  			if (isSameSet(i, j))
  				return;
  			numSets--;
  			int x = findSet(i), y = findSet(j);
  			if (rank[x] > rank[y]) {
  				p[y] = x;
  				setSize[x] += setSize[y];
  			} else {
  				p[x] = y;
  				setSize[y] += setSize[x];
  				if (rank[x] == rank[y])
  					rank[y]++;
  			}
  		}
  
  		public int numDisjointSets() {
  			return numSets;
  		}
  
  		public int sizeOfSet(int i) {
  			return setSize[findSet(i)];
  		}
  
  		public String toString() {
  			return Arrays.toString(p) + "   " + Arrays.toString(rank);
  		}
  	}
  
  	/*
  	 * static class PairPoint{ pair p1; pair p2; public PairPoint(pair p1,pair p2) {
  	 * this.p1=p1; this.p2=p2;
  	 * 
  	 * } public boolean inter(pair p) { int x1=Math.max(p1.x,
  	 * p2.x),x2=Math.min(p1.x, p2.x); int y1=Math.max(p1.y, p2.y),y2=Math.min(p1.y,
  	 * p2.y); if((p.x>=x2 && p.x<=x1) && (p.y>=y2 && p.y<=y1)) return true; return
  	 * false; } public void swap(PairPoint pp) { pp.p1.swap(this.p1);
  	 * pp.p2.swap(this.p2); }
  	 * 
  	 * public String toString () { return p1.toString()+p2.toString(); } public
  	 * boolean equals (PairPoint pp) { if(p1.equals(pp.p1) && p2.equals(pp.p2))
  	 * return true; return false; }
  	 * 
  	 * }
  	 */
  	static class Scanner {
  		StringTokenizer st;
  		BufferedReader br;
  
  		public Scanner(InputStream s) {
  			br = new BufferedReader(new InputStreamReader(s));
  		}
  
  		public Scanner(FileReader r) {
  			br = new BufferedReader(r);
  		}
  
  		public String next() throws IOException {
  			while (st == null || !st.hasMoreTokens())
  				st = new StringTokenizer(br.readLine());
  			return st.nextToken();
  		}
  
  		public String readAllLines(BufferedReader reader) throws IOException {
  			StringBuilder content = new StringBuilder();
  			String line;
  
  			while ((line = reader.readLine()) != null) {
  				content.append(line);
  				content.append(System.lineSeparator());
  			}
  
  			return content.toString();
  		}
  
  		public int nextInt() throws IOException {
  			return Integer.parseInt(next());
  		}
  
  		public long nextLong() throws IOException {
  			return Long.parseLong(next());
  		}
  
  		public String nextLine() throws IOException {
  			return br.readLine();
  		}
  
  		public double nextDouble() throws IOException {
  			String x = next();
  			StringBuilder sb = new StringBuilder("0");
  			double res = 0, f = 1;
  			boolean dec = false, neg = false;
  			int start = 0;
  			if (x.charAt(0) == '-') {
  				neg = true;
  				start++;
  			}
  			for (int i = start; i < x.length(); i++)
  				if (x.charAt(i) == '.') {
  					res = Long.parseLong(sb.toString());
  					sb = new StringBuilder("0");
  					dec = true;
  				} else {
  					sb.append(x.charAt(i));
  					if (dec)
  						f *= 10;
  				}
  			res += Long.parseLong(sb.toString()) / f;
  			return res * (neg ? -1 : 1);
  		}
  
  		public long[] nextlongArray(int n) throws IOException {
  			long[] a = new long[n];
  			for (int i = 0; i < n; i++)
  				a[i] = nextLong();
  			return a;
  		}
  
  		public Long[] nextLongArray(int n) throws IOException {
  			Long[] a = new Long[n];
  			for (int i = 0; i < n; i++)
  				a[i] = nextLong();
  			return a;
  		}
  
  		public int[] nextIntArray(int n) throws IOException {
  			int[] a = new int[n];
  			for (int i = 0; i < n; i++)
  				a[i] = nextInt();
  			return a;
  		}
  
  		public Integer[] nextIntegerArray(int n) throws IOException {
  			Integer[] a = new Integer[n];
  			for (int i = 0; i < n; i++)
  				a[i] = nextInt();
  			return a;
  		}
  
  		public boolean ready() throws IOException {
  			return br.ready();
  		}
  
  	}
  
  }
  