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



public class copy {


    public static boolean checker(long[] arr, long K, long diff) {
        long collect = 0;
        for (int i = 0; i < arr.length; i++) {
            if (arr[i] > diff)
                collect += arr[i] - diff;
        }

        if (collect >= K)
            return true;
        else
            return false;
    }

    public static long search(long[] arr, long K, long R) {
        long l = 0;
        long r = R;

        while (l <= r) {
            long mid = (l + r) / 2;

            if (checker(arr, K, mid)) {
                if (checker(arr, K, mid + 1))
                    l = mid + 1;
                else
                    return mid;
            } else
                r = mid - 1;
        }
        return -1;
    }

    static void sieveOfEratosthenes(int n, ArrayList<Integer> arr, ArrayList<Integer> arr1) {
        // Create a boolean array
        // "prime[0..n]" and
        // initialize all entries
        // it as true. A value in
        // prime[i] will finally be
        // false if i is Not a
        // prime, else true.
        boolean prime[] = new boolean[n + 1];
        for (int i = 0; i <= n; i++)
            prime[i] = true;

        for (int p = 2; p * p <= n; p++) {
            // If prime[p] is not changed, then it is a
            // prime
            if (prime[p] == true) {

                // Update all multiples of p
                for (int i = p * p; i <= n; i += p)
                    prime[i] = false;
            }
        }

        // Print all prime numbers
        int x = 0;
        for (int i = 2; i <= n; i++) {
            if (prime[i] == true) {

                arr.add(i);


            }

        }
        System.out.println(arr.size());
    }

    public static boolean check(String s, int K, char ch) {
        ArrayList<Integer> arr = new ArrayList<>();
        for (int i = 0; i < s.length(); i++) {
            if (s.charAt(i) == ch)
                arr.add(i);
        }
//        if(K==1 && ch=='z')
//            System.out.println(arr);
        if (arr.size() == 0)
            return false;
        if (arr.get(0) >= K)
            return false;
        if (s.length() - 1 - arr.get(arr.size() - 1) >= K)
            return false;
        for (int i = 1; i < arr.size(); i++) {
            if (arr.get(i) - arr.get(i - 1) > K)
                return false;
        }
        return true;
    }

    public static int check(long N) {
        int sum = 0;
        while (N > 0) {
            sum += N % 10;
            N = N / 10;
        }
        return sum;

    }

    public static long call(long N) {
        long l = 1;
        long r = (long) Math.floor(Math.sqrt(N));
        while (l <= r) {
            long mid = (l + r) / 2;
            double left = N / (double) (mid) - mid;
            int right = check(mid);
            System.out.println(mid + " " + left + " " + right);
            if (mid == 10)
                System.out.println(left + " " + right);
            if (left > right)
                l = mid + 1;
            else if (right > left)
                r = mid - 1;
            else
                return mid;
        }
        return -1;
    }

    public static int path(ArrayList<ArrayList<Integer>> arr, int X, int parent, int[] gold, PriorityQueue<Integer> pq) {
        int max = 0;
        ArrayList<Integer> ch = new ArrayList<>();
        for (int i : arr.get(X)) {
            if (i != parent) {
                ch.add(path(arr, i, X, gold, pq));
            }
        }
        Collections.sort(ch, Collections.reverseOrder());
        for (int i = 1; i < ch.size(); i++)
            pq.add(ch.get(i));


        if (ch.size() == 0)
            return gold[X];
        else
            return ch.get(0) + gold[X];

    }

    public static long fac(long N, long mod) {
        if (N == 0)
            return 1;
        return ((N % mod) * (fac(N - 1, mod) % mod)) % mod;
    }

    public static String form(char ch, int freq) {
        String s = "";
        for (int i = 1; i <= freq; i++)
            s += ch;
        return s;
    }

    static long power(long x, long y, long p) {

        // Initialize result
        long res = 1;

        // Update x if it is more than or
        // equal to p
        x = x % p;

        while (y > 0) {

            // If y is odd, multiply x
            // with result
            if (y % 2 == 1)
                res = (res * x) % p;

            // y must be even now
            y = y >> 1; // y = y/2
            x = (x * x) % p;
        }

        return res;
    }

    // Returns n^(-1) mod p
    static long modInverse(long n, long p) {
        return power(n, p - 2, p);
    }

    // Returns nCr % p using Fermat's
    // little theorem.
    static long nCrModPFermat(long n, long r,
                              long p) {

        if (n < r)
            return 0;
        // Base case
        if (r == 0)
            return 1;

        // Fill factorial array so that we
        // can find all factorial of r, n
        // and n-r


//        System.out.println(modInverse(fac(r,p),p));
//        System.out.println(modInverse(fac(n-r,p),p));
        return ((fac(n, p) % p * (modInverse(fac(r, p), p)
                % p)) % p * (modInverse(fac(n - r, p), p)
                % p)) % p;
    }

    public static boolean check(long[] arr, long time, int M) {
        long sum = 0;
        int count = 0;
        for (int i = 0; i < arr.length; i++) {
            sum += arr[i];
            if (sum >= time) {
                ++count;
                sum = 0;
            }
        }

        if (sum >= time)
            ++count;

        return count >= M;
    }

    public static int check(ArrayList<Integer> arr, ArrayList<Integer> arr2) {
        int l = 0, r = 0, ans = 0;
        while (l < arr.size() && r < arr2.size()) {
            if (arr.get(l) < arr2.get(r))
                ++l;
            else if (arr.get(l) > arr2.get(r))
                ++r;
            else {
                ++ans;
                ++l;
                ++r;
            }
        }
        return ans;
    }


    public static int find(int[] parent, int x) {
        if (parent[x] == x)
            return x;
        return find(parent, parent[x]);
    }

    public static void merge(int[] parent, int[] rank, int x, int y) {
        int x1 = find(parent, x);
        int y1 = find(parent, y);
        if (rank[x1] > rank[y1]) {
            parent[y1] = x1;

        } else if (rank[y1] > rank[x1]) {
            parent[x1] = y1;
        } else {
            parent[y1] = x1;
            rank[x1]++;
        }
    }

    public static int check(ArrayList<ArrayList<Integer>> arr, int e1, int e2, int N) {
        boolean[] visited = new boolean[N];
        visited[0] = true;
        int[] dist = new int[N];
        Queue<Integer> queue = new LinkedList<>();
        queue.add(0);
        Arrays.fill(dist, -1);
        dist[0] = 0;
        while (queue.size() > 0) {
            int x = queue.poll();
            for (int i : arr.get(x)) {
                if (!visited[i] || (e1 == x && e2 == i)) {
                    System.out.println(x + " " + dist[x]);
                    dist[i] = dist[x] + 1;
                    visited[i] = true;
                    queue.add(i);
                }
            }

        }


        return dist[N - 1];
    }

    static int N;

    static void rotate90Clockwise(String a[][]) {

        // Traverse each cycle
        for (int i = 0; i < N / 2; i++) {
            for (int j = i; j < N - i - 1; j++) {

                // Swap elements of each cycle
                // in clockwise direction
                String temp = a[i][j];
                a[i][j] = a[N - 1 - j][i];
                a[N - 1 - j][i] = a[N - 1 - i][N - 1 - j];
                a[N - 1 - i][N - 1 - j] = a[j][N - 1 - i];
                a[j][N - 1 - i] = temp;
            }
        }
    }


    public static void moves(String s, int i, int[] movx, int[] movy, int x, int y) {
        if (i >= s.length())
            return;
        //System.out.println(x+" hello "+y);
        if (s.charAt(i) == 'L') {
            movy[i] = y;
            movx[i] = x - 1;
            moves(s, i + 1, movx, movy, x - 1, y);
        } else if (s.charAt(i) == 'R') {
            movy[i] = y;
            movx[i] = x + 1;
            moves(s, i + 1, movx, movy, x + 1, y);
        } else if (s.charAt(i) == 'U') {
            movy[i] = y + 1;
            movx[i] = x;
            moves(s, i + 1, movx, movy, x, y + 1);
        } else {
            movy[i] = y - 1;
            movx[i] = x;
            moves(s, i + 1, movx, movy, x, y - 1);
        }

    }


    public static boolean check(String s, int i, int x, int y, int obsx, int obsy) {
        if (i >= s.length()) {
            if (x == 0 && y == 0)
                return true;
            return false;
        }
        boolean status1 = false, status2 = false, status3 = false, status4 = false;
        //System.out.println(x+" "+y+" "+obsx+" "+obsy+" "+s.charAt(i));
        if (s.charAt(i) == 'L') {
            if (x - 1 == obsx && y == obsy)
                status1 = check(s, i + 1, x, y, obsx, obsy);
            else
                status1 = check(s, i + 1, x - 1, y, obsx, obsy);
            //moves(s,i+1,movx,movy,x-1,y);
        } else if (s.charAt(i) == 'R') {
            if (x + 1 == obsx && y == obsy)
                status2 = check(s, i + 1, x, y, obsx, obsy);
            else
                status2 = check(s, i + 1, x + 1, y, obsx, obsy);
            //moves(s,i+1,movx,movy,x+1,y);
        } else if (s.charAt(i) == 'U') {
            if (y + 1 == obsy && x == obsx)
                status3 = check(s, i + 1, x, y, obsx, obsy);
            else
                status3 = check(s, i + 1, x, y + 1, obsx, obsy);
            //moves(s,i+1,movx,movy,x,y-1);
        } else {
            if (y - 1 == obsy && x == obsx)
                status4 = check(s, i + 1, x, y, obsx, obsy);
            else
                status4 = check(s, i + 1, x, y - 1, obsx, obsy);
        }
        return status1 || status2 || status3 || status4;
    }

    public static int mergeAndCount1(div[] arr, int l,
                                     int m, int r,int[] answer) {

        // Left subarray
        div[] left = Arrays.copyOfRange(arr, l, m + 1);

        // Right subarray
        div[] right = Arrays.copyOfRange(arr, m + 1, r + 1);

        int i = 0, j = 0, k = l, swaps = 0;
        for(int x=0;x<right.length;x++)
            answer[right[x].y]+=binse(left,right[x].x,left.length);

        while (i < left.length && j < right.length) {
            if (left[i].x <= right[j].x)
                arr[k++] = left[i++];
            else {
                //answer[right[j].y]+=binse(left,right[j].x,left.length);
                arr[k++] = right[j++];

            }
        }
        while (i < left.length)
            arr[k++] = left[i++];
        while (j < right.length)
            arr[k++] = right[j++];
        return swaps;
    }

    // Merge sort function
    public static int mergeSortAndCount(div[] arr, int l,
                                        int r,int[] answer) {

        // Keeps track of the inversion count at a
        // particular node of the recursion tree
        int count = 0;

        if (l < r) {
            int m = (l + r) / 2;

            // Total inversion count = left subarray count
            // + right subarray count + merge count

            // Left subarray count
            count += mergeSortAndCount(arr, l, m,answer);

            // Right subarray count
            count += mergeSortAndCount(arr, m + 1, r,answer);

            // Merge count
            count += mergeAndCount1(arr, l, m, r,answer);
        }

        return count;
    }


    public static boolean checker(String s1, String s2, int[] arr, int mid) {
        String s = "";
        int N = s1.length();
        boolean[] visited = new boolean[N];
        for (int i = 0; i <= mid; i++)
            visited[arr[i] - 1] = true;
        for (int i = 0; i < N; i++) {
            if (!visited[i])
                s += s1.charAt(i);
        }

        int l = 0, index = -1;
        while (l < s2.length()) {
            if (s.indexOf(s2.charAt(l), index + 1) == -1)
                return false;
            else {
                index = s.indexOf(s2.charAt(l), index + 1);
                ++l;
            }
        }

        return true;
    }

    public static int check(ArrayList<Integer> possible, int X, int start) {
        int l = start, r = possible.size() - 1;

        while (l <= r) {
            int mid = (l + r) / 2;
            if (possible.get(mid) > X) {
                if (mid - 1 >= start && possible.get(mid - 1) > X)
                    r = mid - 1;
                else
                    return mid;
            } else
                l = mid + 1;
        }

        return -1;
    }


    public static int binse(div[] arr, int X, int N) {
        int l = 0, r = N - 1;
        if(arr[N-1].x<=X)
            return N;
        if(arr[0].x>X)
            return 0;
        while (l <= r) {
            int mid = (l + r) / 2;
            if(arr[mid].x>=X)
            {
                if(mid+1<N && arr[mid+1].x<=X)
                    l=mid+1;
                else
                {
                    //System.out.println(X+" "+mid);
                    return mid;
                }
            }

            else
                l=mid+1;
        }
        return -1;
    }


    public static long dp(long[][] dp, int X, int[] arr, int index, long mod) {
        //System.out.println(index+" "+X);
        if (dp[index][X] != -1)
            return dp[index][X];
        int index1 = index + 1;
        int plus = (X - arr[index1] + 10) % 10;
        long ans = dp(dp, plus, arr, index - 1, mod) % mod;
        for (int i = 0; i < 10; i++) {
            if ((arr[index1] * i) % 10 == X)
                ans = (ans % mod + dp(dp, i, arr, index - 1, mod) % mod) % mod;
        }

        dp[index][X] = ans;
        return ans;


    }

    public static long gcd(long a, long b) {
        if (b == 0)
            return a;

        return gcd(b, a % b);
    }

    public static int check(int x, ArrayList<ArrayList<Integer>> arr, int parent, int dist, long[] ans, int[] child) {
        ans[0] += dist;
        int c = 0;
        for (int i : arr.get(x)) {
            if (i != parent)
                c += check(i, arr, x, dist + 1, ans, child);
        }

        child[x] = c + 1;
        return c + 1;
    }

    public static void check(int x, int parent, ArrayList<ArrayList<Integer>> arr, int[] child, long[] ans) {
        ans[x] = ans[parent] - (child[x]) + (arr.size() - child[x]);

        for (int i : arr.get(x)) {
            if (i != parent) {
                check(i, x, arr, child, ans);
            }
        }
    }

    public static void leftRotatebyOne(int arr[], int n) {
        int i, temp;
        temp = arr[0];
        for (i = 0; i < n - 1; i++)
            arr[i] = arr[i + 1];
        arr[n - 1] = temp;
    }

    public static void tick(char[][] ch, int N, int M, int x, int y, int k, int[][] copy) {

        int c = 1, size = 0;
        //System.out.println(x+" "+y);
        while (x - c >= 0 && y - c >= 0 && y + c < M && ch[x - c][y - c] == '*' && ch[x - c][y + c] == '*') {
            ++size;

            ++c;

        }
        //System.out.println(size);
        c -= 1;
        while (c >= 0) {

            copy[x - c][y - c] = Math.max(copy[x - c][y - c], size);
            copy[x - c][y + c] = Math.max(copy[x - c][y + c], size);

            --c;
        }


    }


    public static void main(String[] args) throws IOException {
        Reader.init(System.in);
        BufferedWriter output = new BufferedWriter(new OutputStreamWriter(System.out));


        int T = Reader.nextInt();
        A:
        for (int m = 1; m <= T; m++) {
            int N = Reader.nextInt();
           div[] arr=new div[N];
           for(int i=0;i<N;i++)
               arr[i]=new div(Reader.nextInt(),i);
           int[] answer=new int[N];
           mergeSortAndCount(arr,0,N-1,answer);
           int ans=0;
//           for(int i=0;i<N;i++)
//               System.out.println(answer[i]);
           for(int i=0;i<N;i++)
           {
               ans+=Math.min(answer[i],i-answer[i]);
           }

           output.write(ans+"\n");





        }
        output.flush();


    }
}



class Reader {
    static BufferedReader reader;
    static StringTokenizer tokenizer;

    static void init(InputStream input) {
        reader = new BufferedReader(
                new InputStreamReader(input));
        tokenizer = new StringTokenizer("");
    }

    static String next() throws IOException {
        while (!tokenizer.hasMoreTokens()) {
            tokenizer = new StringTokenizer(
                    reader.readLine());
        }
        return tokenizer.nextToken();
    }

    static int nextInt() throws IOException {
        return Integer.parseInt(next());
    }

    static long nextLong() throws IOException {
        return Long.parseLong(next());
    }

    static double nextDouble() throws IOException {
        return Double.parseDouble(next());
    }
}

class div
{
    int x,y;
    div(int x1,int y1)
    {
        x=x1;
        y=y1;
    }
}


