CODESPTB - Insertion Sort

题意翻译

给定一个长度为 $n$ 的序列,求使其交换至有序(从小到大)的最少交换次数(逆序对) **【输入格式】** 本题有多组数据 输入一个正整数 $T$,表示有 $T$ 组数据 对于每组数据 一个正整数 $n$ $n$ 个正整数表示这个序列 **【输出格式】** 换行输出每组序列的最小交换次数 **【数据范围】** $1 \le T \le 5$,$1 \le n \le {10}^5$,$1 \le a_i \le {10}^6$。

题目描述

Insertion Sort is a classical sorting technique. One variant of insertion sort works as follows when sorting an array a\[1..N\] in non-descending order: ``` for i <- 2 to N     j <- i     while j > 1 and a[j] < a[j - 1]        swap a[j] and a[j - 1]        j <- j - 1 ``` The pseudocode is simple to follow. In the ith step, element a\[i\] is inserted in the sorted sequence a\[1..i - 1\]. This is done by moving a\[i\] backward by swapping it with the previous element until it ends up in it's right position. As you probably already know, the algorithm can be really slow. To study this more, you want to find out the number of times the swap operation is performed when sorting an array.

输入输出格式

输入格式


The first line contains the number of test cases T. T test cases follow. The first line for each case contains N, the number of elements to be sorted. The next line contains N integers a\[1\],a\[2\]...,a\[N\].

输出格式


Output T lines, containing the required answer for each test case.

输入输出样例

输入样例 #1

2
5
1 1 1 2 2
5
2 1 3 1 2

输出样例 #1

0
4

说明

1 <= T <= 5 1 <= N <= 100000 1 <= a[i] <= 1000000