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.
							/*
							ID: abdelra29
		LANG: JAVA
		PROG: zerosum
							*/
								/*
								TO LEARN
						
								2-euler tour
							
								*/
								/*
								TO SOLVE 
								*/
								/*
								bit manipulation shit
								1-Computer Systems: A Programmer's Perspective
								2-hacker's delight
								*/
								/*
								TO WATCH
								
								*/
								            import java.util.*;
										    import java.math.*;
										    import java.io.*; 
										    import java.text.DecimalFormat;
										    import java.util.stream.Collectors;


										       public class A{
								            static FastScanner scan=new FastScanner();
											     public static PrintWriter out = new PrintWriter (new BufferedOutputStream(System.out));
			static int BIT[];
			static int BIT2[];
			static int n;
			static int get(int x){
				int res=0;
				x--;
				while(x>=1)
				{
					res+=BIT[x];
					x-=(x&-x);
				}
				return res;
			}
			static void update(int x,int val)
			{
				//x++;
				while(x<=n)
				{
					BIT[x]+=val;
					x+=(x&-x);
				}
			}
			static int get2(int x)
			{
				int res=0;
				x++;
				while(x<=n)
				{
					res+=BIT2[x];
					x+=(x&-x);
				}
				return res;
			}
			static void update2(int x,int val)
			{
				int res=0;
				//x--;
				while(x>=1)
				{
					//res+=BIT2[x];
					BIT2[x]+=val;
					x-=(x&-x);
				}
			}

				public static void main(String[] args)  throws Exception 
								      {
								 /*
								 very important tips 
								 1-just fucking think backwards once in your shitty life
								 2-consider brute forcing and finding some patterns and observations
								 3-when you're in contest don't get out because you think there is no enough time
								 4-don't get stuck on one approach 
								 */
							   
	//			scan=new FastScanner("D:\\usaco test data\\WW.txt");
	//			out = new PrintWriter("D:\\usaco test data\\WWW.txt");

							
										 							 /*
										 READING 
								
										 3-Introduction to DP with Bit-masking codeforces
										 4-Bit Manipulation hacker-earth
										 5-read more about mobious and inclusion-exclusion 
					 				     6-read more about Fermat little theorem
										 */
										 /*
										   
										 */

					 			
								     
	int tt=1;

									tt=scan.nextInt();
									int T=tt;
									 outer:while(tt-->0)
									    {
									    n=scan.nextInt();
									   BIT=new int[n+1];
									   BIT2=new int[n+1];
									   //update2(3,1);
									  // System.out.println(get2(2));
									   int arr[]=new int[n];
									   int sorted[]=new int[n];
									   for(int i=0;i<n;i++)
									   {
									   	arr[i]=scan.nextInt()+((int)(1e9+1));
									   	sorted[i]=arr[i];
									   }
									   Map<Integer,TreeSet<Integer>>map=new HashMap<Integer,TreeSet<Integer>>();
									   for(int i=0;i<n;i++)
									   {
									   	if(map.containsKey(arr[i]))
									   	{
									   		map.get(arr[i]).add(i);
									   	}
									   	else 
									   	{
									   		map.put(arr[i],new TreeSet());
									   		map.get(arr[i]).add(i);
									   	}
									   }
									   int cnt=1;
									   Arrays.sort(sorted);
									   for(int i=0;i<n;)
									   {
									   	arr[map.get(sorted[i]).pollFirst()]=cnt;
									   	i++;
									   	while(i<n&&sorted[i]==sorted[i-1])
									   	{
									   		arr[map.get(sorted[i]).pollFirst()]=cnt;
									   		i++;
									   	}
									   	cnt++;
									   }
									  // out.println(Arrays.toString(arr));
									  long res=0;
									   for(int i=0;i<n;i++)
									   {
									   //	out.println(arr[i]+" "+get(arr[i])+" "+get2(arr[i]));
									  if(get(arr[i])<=get2(arr[i]))
									  {
									  	res+=get(arr[i]);
									  }
									  else res+=get2(arr[i]);
									  update(arr[i],1);
									  update2(arr[i],1);
									   }
									   out.println(res);





									    									    	
	  			   	
		 }							
		
	        

				out.close();
							}
							
							

							static class special implements Comparable<special>{
							int cnt,idx;
							String s;
							public special(int cnt,int idx,String s)
							{
								this.cnt=cnt;
								this.idx=idx;
								this.s=s;
							}

								 @Override
										            public int hashCode() {
										                return (int)42;
										            }
								  @Override
										            public boolean equals(Object o){
										            //	System.out.println("FUCK");
										                if (o == this) return true;
										                if (o.getClass() != getClass()) return false;
										                special t = (special)o;
										                return t.cnt == cnt && t.idx == idx;
										            }
										            public int compareTo(special o1)
										            {
										            	if(o1.cnt==cnt)
										            	{
										            		return o1.idx-idx;
										            	}
										            	return o1.cnt-cnt;
										            }
							}
				
										   
										     static long binexp(long a,long n)
										    {
										        if(n==0)
										            return 1;
										        long res=binexp(a,n/2);
										        if(n%2==1)
										            return res*res*a;
										        else 
										            return res*res;
										    }
										     
										    static long powMod(long base, long exp, long mod) {
										           if (base == 0 || base == 1) return base;
										           if (exp == 0) return 1;
										           if (exp == 1) return (base % mod+mod)%mod;
										           long R = (powMod(base, exp/2, mod) % mod+mod)%mod;
										           R *= R;
										           R %= mod;
										           if ((exp & 1) == 1) {
										               return (base * R % mod+mod)%mod;
										           }
										           else return (R %mod+mod)%mod;
										       }
										    static double dis(double x1,double y1,double x2,double y2)
										    {
										        return Math.sqrt((x1-x2)*(x1-x2)+(y1-y2)*(y1-y2));
										    }
										    static long mod(long x,long y)
										        {
										            if(x<0)
										                x=x+(-x/y+1)*y;
										            return x%y;
										        }
										     public static  long pow(long b, long e) {
										                long r = 1;
										                while (e > 0) {
										                    if (e % 2 == 1) r = r * b ;
										                    b = b * b;
										                    e >>= 1;
										                }
										                return r;
										            }
										    private static void sort(int[] arr) {
										            List<Integer> list = new ArrayList<>();
										            for (int object : arr) list.add(object);
										            Collections.sort(list);
										        //Collections.reverse(list);
										            for (int i = 0; i < list.size(); ++i) arr[i] = list.get(i);
										        }
										    private static void sort2(long[] arr) {
										            List<Long> list = new ArrayList<>();
										            for (Long object : arr) list.add(object);
										            Collections.sort(list);
										        Collections.reverse(list);
										            for (int i = 0; i < list.size(); ++i) arr[i] = list.get(i);
										        }
										     static class FastScanner
								{
								    private int BS = 1 << 16;
								    private char NC = (char) 0;
								    private byte[] buf = new byte[BS];
								    private int bId = 0, size = 0;
								    private char c = NC;
								    private double cnt = 1;
								    private BufferedInputStream in;
								 
								    public FastScanner() {
								        in = new BufferedInputStream(System.in, BS);
								    }
								 
								    public FastScanner(String s) {
								        try {
								            in = new BufferedInputStream(new FileInputStream(new File(s)), BS);
								        } catch (Exception e) {
								            in = new BufferedInputStream(System.in, BS);
								        }
								    }
								 
								    private char getChar() {
								        while (bId == size) {
								            try {
								                size = in.read(buf);
								            } catch (Exception e) {
								                return NC;
								            }
								            if (size == -1) return NC;
								            bId = 0;
								        }
								        return (char) buf[bId++];
								    }
								 
								    public int nextInt() {
								        return (int) nextLong();
								    }
								 
								    public int[] nextInts(int N) {
								        int[] res = new int[N];
								        for (int i = 0; i < N; i++) {
								            res[i] = (int) nextLong();
								        }
								        return res;
								    }
								 
								    public long[] nextLongs(int N) {
								        long[] res = new long[N];
								        for (int i = 0; i < N; i++) {
								            res[i] = nextLong();
								        }
								        return res;
								    }
								 
								    public long nextLong() {
								        cnt = 1;
								        boolean neg = false;
								        if (c == NC) c = getChar();
								        for (; (c < '0' || c > '9'); c = getChar()) {
								            if (c == '-') neg = true;
								        }
								        long res = 0;
								        for (; c >= '0' && c <= '9'; c = getChar()) {
								            res = (res << 3) + (res << 1) + c - '0';
								            cnt *= 10;
								        }
								        return neg ? -res : res;
								    }
								 
								    public double nextDouble() {
								        double cur = nextLong();
								        return c != '.' ? cur : cur + nextLong() / cnt;
								    }
								 
								    public double[] nextDoubles(int N) {
								        double[] res = new double[N];
								        for (int i = 0; i < N; i++) {
								            res[i] = nextDouble();
								        }
								        return res;
								    }
								 
								    public String next() {
								        StringBuilder res = new StringBuilder();
								        while (c <= 32) c = getChar();
								        while (c > 32) {
								            res.append(c);
								            c = getChar();
								        }
								        return res.toString();
								    }
								 
								    public String nextLine() {
								        StringBuilder res = new StringBuilder();
								        while (c <= 32) c = getChar();
								        while (c != '\n') {
								            res.append(c);
								            c = getChar();
								        }
								        return res.toString();
								    }
								 
								    public boolean hasNext() {
								        if (c > 32) return true;
								        while (true) {
								            c = getChar();
								            if (c == NC) return false;
								            else if (c > 32) return true;
								        }
								    }
								}

										     static class Pair implements Comparable<Pair>{
										            public long x, y,z;
										            public Pair(long x1, long y1,long z1) {
										                x=x1;
										                y=y1;
										                z=z1;
										            }
										             public Pair(long x1, long y1) {
										                x=x1;
										                y=y1;
										    
										            }
										            
										            @Override
										            public int hashCode() {
										                return (int)(x + 31 * y);
										            }
										            public String toString() {
										                return x + " " + y+" "+z;
										            }
										            @Override
										            public boolean equals(Object o){
										                if (o == this) return true;
										                if (o.getClass() != getClass()) return false;
										                Pair t = (Pair)o;
										                return t.x == x && t.y == y&&t.z==z;
										            }
										    public int compareTo(Pair o)
										    {
										    								  	
										  if(x==o.x)
										  	return (int)(y-o.y);
										    	return (int)(x-o.x);
										     
										        }
										     
										    }
										}
										
										    
										   

										     
