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.
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.math.BigDecimal;
import java.math.RoundingMode;
import java.util.*;
import java.io.File;
import java.io.FileDescriptor;
import java.io.FileOutputStream;
import java.io.OutputStream;
import java.io.UncheckedIOException;
import java.lang.Thread.State;
import java.lang.reflect.Field;
import java.nio.CharBuffer;
import java.nio.charset.CharacterCodingException;
import java.nio.charset.CharsetEncoder;
import java.nio.charset.StandardCharsets;

public class Main {
	static final long MOD1=1000000007;
	static final long MOD=998244353;
	static int ans=0;
	public static void main(String[] args){
		PrintWriter out = new PrintWriter(System.out);
		InputReader sc=new InputReader(System.in);
		int t = sc.nextInt();
		for (int i = 0; i <t; i ++) {
			int n = sc.nextInt();
			long[] p = sc.nextLongArray(n);
			out.println(solve(n, p));
		}
		out.flush();
	}
	static long solve(int n,long[] p){
		HashMap<Long,Integer> map = compress(p,true);
		SegTree<Long> segTree = new SegTree<Long>(map.size(),(x,y)->x+y,0l);
		long[] dp = new long[n+1];
		for (int i = 1; i < dp.length; i++) {
			long c = Math.min(segTree.prod(0,map.get(p[i-1])),segTree.prod(map.get(p[i-1])+1,map.size()));
			dp[i] = dp[i-1] + c;
			segTree.set(map.get(p[i-1]),segTree.get(map.get(p[i-1]))+1);
		}
		return dp[n];
	}
	static HashMap<Long, Integer> compress(long[] A,boolean is_duplication){
		HashMap<Long, Integer> hashMap = new HashMap<>();
		if (is_duplication) {
			TreeSet<Long> treeSet = new TreeSet<>();
			int now = 0;
			for (int i = 0; i < A.length; i++) {
				treeSet.add(A[i]);
			}
			while (!treeSet.isEmpty()) {
				long a = treeSet.pollFirst();
				hashMap.put(a, now);
				now++;
			}
		}else {
			PriorityQueue<Long> priorityQueue = new PriorityQueue<>();
			int now = 0;
			for (int i = 0; i < A.length; i++) {
				priorityQueue.add(A[i]);
			}
			while (!priorityQueue.isEmpty()) {
				long a = priorityQueue.poll();
				hashMap.put(a, now);
				now++;
			}
		}
		return hashMap;
	}//is_duplicationがtrueのとき重複をつぶす。
	static class InputReader { 
		private InputStream in;
		private byte[] buffer = new byte[1024];
		private int curbuf;
		private int lenbuf;
		public InputReader(InputStream in) {
			this.in = in;
			this.curbuf = this.lenbuf = 0;
		}
		public boolean hasNextByte() {
			if (curbuf >= lenbuf) {
				curbuf = 0;
				try {
					lenbuf = in.read(buffer);
				} catch (IOException e) {
					throw new InputMismatchException();
				}
				if (lenbuf <= 0)
					return false;
			}
			return true;
		}
 
		private int readByte() {
			if (hasNextByte())
				return buffer[curbuf++];
			else
				return -1;
		}
 
		private boolean isSpaceChar(int c) {
			return !(c >= 33 && c <= 126);
		}
 
		private void skip() {
			while (hasNextByte() && isSpaceChar(buffer[curbuf]))
				curbuf++;
		}
 
		public boolean hasNext() {
			skip();
			return hasNextByte();
		}
 
		public String next() {
			if (!hasNext())
				throw new NoSuchElementException();
			StringBuilder sb = new StringBuilder();
			int b = readByte();
			while (!isSpaceChar(b)) {
				sb.appendCodePoint(b);
				b = readByte();
			}
			return sb.toString();
		}
 
		public int nextInt() {
			if (!hasNext())
				throw new NoSuchElementException();
			int c = readByte();
			while (isSpaceChar(c))
				c = readByte();
			boolean minus = false;
			if (c == '-') {
				minus = true;
				c = readByte();
			}
			int res = 0;
			do {
				if (c < '0' || c > '9')
					throw new InputMismatchException();
				res = res * 10 + c - '0';
				c = readByte();
			} while (!isSpaceChar(c));
			return (minus) ? -res : res;
		}
 
		public long nextLong() {
			if (!hasNext())
				throw new NoSuchElementException();
			int c = readByte();
			while (isSpaceChar(c))
				c = readByte();
			boolean minus = false;
			if (c == '-') {
				minus = true;
				c = readByte();
			}
			long res = 0;
			do {
				if (c < '0' || c > '9')
					throw new InputMismatchException();
				res = res * 10 + c - '0';
				c = readByte();
			} while (!isSpaceChar(c));
			return (minus) ? -res : res;
		}
 
		public double nextDouble() {
			return Double.parseDouble(next());
		}
 
		public int[] nextIntArray(int n) {
			int[] a = new int[n];
			for (int i = 0; i < n; i++)
				a[i] = nextInt();
			return a;
		}
		public double[] nextDoubleArray(int n) {
			double[] a = new double[n];
			for (int i = 0; i < n; i++)
				a[i] = nextDouble();
			return a;
		}
		public long[] nextLongArray(int n) {
			long[] a = new long[n];
			for (int i = 0; i < n; i++)
				a[i] = nextLong();
			return a;
		}
 
		public char[][] nextCharMap(int n, int m) {
			char[][] map = new char[n][m];
			for (int i = 0; i < n; i++)
				map[i] = next().toCharArray();
			return map;
		}
	}
}
//funはlamda式で定義
//prodで取得,setで更新(一点加算なら更新でおｋ)
//二ブタンも出来る
//SegTree<Integer> segTree=new SegTree<Integer>(N, (x,y)->x+y, 0);使用例
class SegTree<S> {
	    final int MAX;

	    final int N;
	    final java.util.function.BinaryOperator<S> op;
	    final S E;

	    final S[] data;

	    @SuppressWarnings("unchecked")
	    public SegTree(int n, java.util.function.BinaryOperator<S> op, S e) {
	        this.MAX = n;
	        int k = 1;
	        while (k < n) k <<= 1;
	        this.N = k;
	        this.E = e;
	        this.op = op;
	        this.data = (S[]) new Object[N << 1];
	        java.util.Arrays.fill(data, E);
	    }

	    public SegTree(S[] dat, java.util.function.BinaryOperator<S> op, S e) {
	        this(dat.length, op, e);
	        build(dat);
	    }

	    private void build(S[] dat) {
	        int l = dat.length;
	        System.arraycopy(dat, 0, data, N, l);
	        for (int i = N - 1; i > 0; i--) {
	            data[i] = op.apply(data[i << 1 | 0], data[i << 1 | 1]);
	        }
	    }

	    public void set(int p, S x) {
	        exclusiveRangeCheck(p);
	        data[p += N] = x;
	        p >>= 1;
	        while (p > 0) {
	            data[p] = op.apply(data[p << 1 | 0], data[p << 1 | 1]);
	            p >>= 1;
	        }
	    }

	    public S get(int p) {
	        exclusiveRangeCheck(p);
	        return data[p + N];
	    }

	    public S prod(int l, int r) {
	        if (l > r) {
	            throw new IllegalArgumentException(
	                String.format("Invalid range: [%d, %d)", l, r)
	            );
	        }
	        inclusiveRangeCheck(l);
	        inclusiveRangeCheck(r);
	        S sumLeft = E;
	        S sumRight = E;
	        l += N; r += N;
	        while (l < r) {
	            if ((l & 1) == 1) sumLeft = op.apply(sumLeft, data[l++]);
	            if ((r & 1) == 1) sumRight = op.apply(data[--r], sumRight);
	            l >>= 1; r >>= 1;
	        }
	        return op.apply(sumLeft, sumRight);
	    }

	    public S allProd() {
	        return data[1];
	    }

	    public int maxRight(int l, java.util.function.Predicate<S> f) {
	        inclusiveRangeCheck(l);
	        if (!f.test(E)) {
	            throw new IllegalArgumentException("Identity element must satisfy the condition.");
	        }
	        if (l == MAX) return MAX;
	        l += N;
	        S sum = E;
	        do {
	            l >>= Integer.numberOfTrailingZeros(l);
	            if (!f.test(op.apply(sum, data[l]))) {
	                while (l < N) {
	                    l = l << 1;
	                    if (f.test(op.apply(sum, data[l]))) {
	                        sum = op.apply(sum, data[l]);
	                        l++;
	                    }
	                }
	                return l - N;
	            }
	            sum = op.apply(sum, data[l]);
	            l++;
	        } while ((l & -l) != l);
	        return MAX;
	    }

	    public int minLeft(int r, java.util.function.Predicate<S> f) {
	        inclusiveRangeCheck(r);
	        if (!f.test(E)) {
	            throw new IllegalArgumentException("Identity element must satisfy the condition.");
	        }
	        if (r == 0) return 0;
	        r += N;
	        S sum = E;
	        do {
	            r--;
	            while (r > 1 && (r & 1) == 1) r >>= 1;
	            if (!f.test(op.apply(data[r], sum))) {
	                while (r < N) {
	                    r = r << 1 | 1;
	                    if (f.test(op.apply(data[r], sum))) {
	                        sum = op.apply(data[r], sum);
	                        r--;
	                    }
	                }
	                return r + 1 - N;
	            }
	            sum = op.apply(data[r], sum);
	        } while ((r & -r) != r);
	        return 0;
	    }

	    private void exclusiveRangeCheck(int p) {
	        if (p < 0 || p >= MAX) {
	            throw new IndexOutOfBoundsException(
	                String.format("Index %d out of bounds for the range [%d, %d).", p, 0, MAX)
	            );
	        }
	    }

	    private void inclusiveRangeCheck(int p) {
	        if (p < 0 || p > MAX) {
	            throw new IndexOutOfBoundsException(
	                String.format("Index %d out of bounds for the range [%d, %d].", p, 0, MAX)
	            );
	        }
	    }
	}
