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.*;
import java.util.*;

public class CodeForces{
    /*****************************************WRITING CODE STARTS HERE******************************************/
    static class MergeSortTree {
        ArrayList<Integer>[] segTree;
        public MergeSortTree(int[] arr, int n){
            segTree = new ArrayList[4*n];
            for(int i=0;i<segTree.length;i++)
                segTree[i] = new ArrayList<>();
            build(0,n-1,0,arr);
        }
        private void merge(ArrayList<Integer> left,ArrayList<Integer> right,ArrayList<Integer> parent){
            int i=0,j=0;
            int n = left.size(),m=right.size();
            while(i<n && j<m){
                if(left.get(i) <= right.get(j))
                    parent.add(left.get(i++));
                else parent.add(right.get(j++));
            }
            while(i<n)parent.add(left.get(i++));
            while(j<m)parent.add(right.get(j++));
        }
        private void build(int stL,int stR,int stIndex,int[] arr){
            if(stL == stR){ //leaf node
                segTree[stIndex].add(arr[stL]);
                return;
            }
            int mid = (stR - stL)/2 + stL;
            build(stL,mid,2*stIndex+1,arr);
            build(mid+1,stR,2*stIndex+2,arr);
            merge(segTree[2*stIndex+1],segTree[2*stIndex+2],segTree[stIndex]);
        }
        private int getMinCount(int stL,int stR,int qL,int qR,int val,int stIndex){
            if(qL>stR || qR<stL)return 0;
            if(qL<=stL && qR>=stR){
                int l = 0;
                int r = segTree[stIndex].size()-1;
                int count = -1;
                while(l<=r){
                    int mid = (r-l)/2 + l;
                    if(segTree[stIndex].get(mid) < val){
                        count = mid;
                        l = mid+1;
                    }else r = mid-1;
                }
                return count+1;
            }
            int stMid = (stR - stL)/2 + stL;
            return getMinCount(stL,stMid,qL,qR,val,2*stIndex+1)
                    + getMinCount(stMid+1,stR,qL,qR,val,2*stIndex+2);
        }
        private int getMaxCount(int stL,int stR,int qL,int qR,int val,int stIndex){
            if(qL>stR || qR<stL)return 0;
            if(qL<=stL && qR>=stR){
                int l = 0;
                int r = segTree[stIndex].size()-1;
                int count = segTree[stIndex].size();
                while(l<=r){
                    int mid = (r-l)/2 + l;
                    if(segTree[stIndex].get(mid) > val){
                        count = mid;
                        r = mid-1;
                    }else l = mid+1;
                }
                return segTree[stIndex].size() - count;
            }
            int stMid = (stR - stL)/2 + stL;
            return getMaxCount(stL,stMid,qL,qR,val,2*stIndex+1)
                    + getMaxCount(stMid+1,stR,qL,qR,val,2*stIndex+2);
        }
    }
    public static void solve(int tCase)throws IOException {
        int n = sc.nextInt();
        int [] arr = new int[n];
        for(int i=0;i<n;i++)arr[i] = sc.nextInt();
        MergeSortTree mergeSortTree = new MergeSortTree(arr,n);
        long ans  = 0;
        for(int i=0;i<n;i++){
            int countGreater = mergeSortTree.getMaxCount(0,n-1,0,i,arr[i],0);
            int countSmaller = mergeSortTree.getMinCount(0,n-1,0,i,arr[i],0);
           ans += Math.min(countGreater,countSmaller);
        }
        out.println(ans);
    }

    /*****************************************WRITING CODE ENDS HERE******************************************/
    public static void main(String[] args) throws IOException{
        openIO();
        int testCase = 1;
        testCase = sc.nextInt();
        for (int i = 1; i <= testCase; i++) solve(i);
        closeIO();
    }
    static FastestReader sc;
    static PrintWriter out;
    private static void openIO() throws IOException{
        sc = new FastestReader();
        out = new PrintWriter(System.out);
    }

    /**************************************HELPER FUNCTION STARTS HERE ************************************/

    public static final int mod = (int) 1e9 +7;
    private static final int mod2 =  998244353;
    public static final int inf_int = (int) 2e9;
    public static  final long inf_long = (long) 4e18;

    // euclidean algorithm time O(max (loga ,logb))
    public static long _gcd(long a, long b) {
        long x = Math.min(a, b);
        long y = Math.max(a, b);
        if (y % x == 0) return x;
        return _gcd(y % x, x);
    }

    public static long _lcm(long a, long b) {
        // lcm(a,b) * gcd(a,b) = a * b
        return (a / _gcd(a, b)) * b;
    }
    // binary exponentiation time O(logn)
    public static long _power(long x, long n) {
        long ans = 1;
        while (n > 0) {
            if ((n & 1) == 1) {
                ans *= x;
                ans %= mod;
                n--;
            } else {
                x *= x;
                x %= mod;
                n >>= 1;
            }
        }
        return ans;
    }
    //sieve/first divisor time : O(mx * log ( log (mx) ) )
    public static int[]  seive(int mx){
        int[] firstDivisor = new int[mx+1];
        for(int i=0;i<=mx;i++)firstDivisor[i] = i;
        for(int i=2;i*i<=mx;i++)
            if(firstDivisor[i] == i)
                for(int j = i*i;j<=mx;j+=i)
                    firstDivisor[j] = i;
        return firstDivisor;
    }


    /**************************************HELPER FUNCTION ENDS HERE ************************************/

    /*****************************************FAST INPUT STARTS HERE *************************************/

    public static void closeIO() throws IOException{
        out.flush();
        out.close();
        sc.close();
    }
    private static final class FastestReader {
        private static final int BUFFER_SIZE = 1 << 16;
        private final DataInputStream din;
        private final byte[] buffer;
        private int bufferPointer, bytesRead;

        public FastestReader() {
            din = new DataInputStream(System.in);
            buffer = new byte[BUFFER_SIZE];
            bufferPointer = bytesRead = 0;
        }

        public FastestReader(String file_name) throws IOException {
            din = new DataInputStream(new FileInputStream(file_name));
            buffer = new byte[BUFFER_SIZE];
            bufferPointer = bytesRead = 0;
        }

        private static boolean isSpaceChar(int c) { return !(c >= 33 && c <= 126); }

        private int skip() throws IOException {
            int b;
            //noinspection StatementWithEmptyBody
            while ((b = read()) != -1 && isSpaceChar(b)) {}
            return b;
        }

        public String next() throws IOException {
            int b = skip();
            final StringBuilder sb = new StringBuilder();
            while (!isSpaceChar(b)) { // when nextLine, (isSpaceChar(b) && b != ' ')
                sb.appendCodePoint(b);
                b = read();
            }
            return sb.toString();
        }

        public int nextInt() throws IOException {
            int ret = 0;
            byte c = read();
            while (c <= ' ') {
                c = read();
            }
            final boolean neg = c == '-';
            if (neg) { c = read(); }
            do {
                ret = ret * 10 + c - '0';
            } while ((c = read()) >= '0' && c <= '9');

            if (neg) { return -ret; }
            return ret;
        }

        public long nextLong() throws IOException {
            long ret = 0;
            byte c = read();
            while (c <= ' ') { c = read(); }
            final boolean neg = c == '-';
            if (neg) { c = read(); }
            do {
                ret = ret * 10 + c - '0';
            } while ((c = read()) >= '0' && c <= '9');
            if (neg) { return -ret; }
            return ret;
        }

        public double nextDouble() throws IOException {
            double ret = 0, div = 1;
            byte c = read();
            while (c <= ' ') { c = read(); }
            final boolean neg = c == '-';
            if (neg) { c = read(); }

            do {
                ret = ret * 10 + c - '0';
            } while ((c = read()) >= '0' && c <= '9');

            if (c == '.') {
                while ((c = read()) >= '0' && c <= '9') {
                    ret += (c - '0') / (div *= 10);
                }
            }

            if (neg) { return -ret; }
            return ret;
        }

        private void fillBuffer() throws IOException {
            bytesRead = din.read(buffer, bufferPointer = 0, BUFFER_SIZE);
            if (bytesRead == -1) { buffer[0] = -1; }
        }

        private byte read() throws IOException {
            if (bufferPointer == bytesRead) { fillBuffer(); }
            return buffer[bufferPointer++];
        }

        public void close() throws IOException {
            din.close();
        }

    }
    /*****************************************FAST INPUT ENDS HERE *************************************/
}