Magic Pairs Solution

Problem

Alexandra has some distinct integer numbers a1,a2...an. Count number of pairs (i,j) such that:

1≤ i ≤ n 1≤ j ≤ n ai < aj

 

Input

The first line of the input contains an integer T denoting the number of test cases. The description of T test cases follows.The first line of each test case contains a single integer n denoting the number of numbers Alexandra has. The second line contains n space-separated distinct integers a1, a2, ..., an denoting these numbers.

 

Output

For each test case, output a single line containing number of pairs for corresponding test case.

 

Constraints

• 1 ≤ T ≤ 4
• 1 ≤ n ≤ 100000
• 0 ≤ ai ≤ 109
• All the ai are distinct

Sample 1:

Input

Output

2
2
12 11
3
13 11 12

1
3

Explanation:

Case 1: Only one such pair of (i, j) indices exists: (2,1), since a2 < a1.

Case 2: 3 possible pairs of indices: (2,1), (2,3), (3,1)

Program :

 import java.util.Scanner;

public class Main

{

public static void main(String[] args) {

Scanner sr = new Scanner(System.in);

int t = sr.nextInt();

for (int c = 0; c < t; c++) {

int n = sr.nextInt();

int[] a = new int[n];

for (int i = 0; i < a.length; i++) {

a[i] = sr.nextInt();

}

System.out.println(solve(a));

}

sr.close();

}

static long solve(int[] a) {

return (long) a.length * (a.length - 1) / 2;

}

}