Sorting

Time limit1sMemory limit128 MB

Summary

Count the swaps made by a given selection-style double loop on an array.

Level: Medium5 of 10
Topics: Sorting, Array, Math
Solved: No attempts yet

Statement

Genetic Programming is a method for automatically constructing computer programs. A Genetic Programming algorithm tries to find a program that, for some input, produces a desired result. It is an evolutionary method: the search for a suitable program is carried out through artificial evolution, a mechanism modeled on biological evolution.

Using Genetic Programming, the integer-sorting algorithm sort() shown below (in C) was evolved. This algorithm is correct and sorts the numbers from largest to smallest. Its innermost loop calls the helper procedure swap(). Can you quickly count how many times swap() runs for a given array $t$ ?

void swap(int *a, int *b)
{
    int tmp = *a;
    *a = *b;
    *b = tmp;
}
void sort(int t[], int N)
{
    int i, j;
    for (i = 0; i < N; ++i)
        for (j = 0; j < N; ++j)
            if (t[i] > t[j])
                swap(&t[i], &t[j]);
}

Input

The first line contains a natural number $d$ ( $1 \le d \le 100$ ), the number of tests.

For each test, the first line contains $n$ ( $1 \le n \le 10^5$ ), the size of the array $t$ . The second line contains the $n$ elements of $t$ , where $-10^9 \le t_i \le 10^9$ for $i = 1 \dots n$ .

Output

For each test, print on a single line the number of times the swap() procedure is called.

Examples3

Example 1
Input
```
2
6
1 2 3 4 5 6
6
6 1 4 2 100 0
```
Expected output
```
15
10
```
Example 2
Input
```
1
4
1 2 3 4
```
Expected output
```
6
```
Example 3
Input
```
1
5
5 4 3 2 1
```
Expected output
```
8
```