Paimon 정렬

Paimon은 버블 정렬과 비슷하지만 몇 가지 차이가 있는 새로운 정렬 알고리즘을 방금 만들었다. 이 알고리즘은 길이 $n$인 1부터 시작하는 인덱스의 수열 $A$를 입력받아 정렬한다. 의사 코드는 다음과 같다.

함수 1: 정렬 알고리즘

1. function Sort(A)
2.     for i ← 1 to n do // n은 A의 원소 개수이다
3.         for j ← 1 to n do
4.             if a_i < a_j then // a_i는 A의 i번째 원소이다
5.                 a_i와 a_j를 교환한다

이 알고리즘이 수열을 정렬한다고 믿기 어렵다면 직접 증명해 보라. 그것도 과제에 포함된다.

길이 $n$인 정수 수열 $A = a_1, a_2, \cdots, a_n$이 주어진다. 각 $1 \le k \le n$에 대해 길이 $k$인 접두사 $A_k = a_1, a_2, \cdots, a_k$를 구하고, SORT($A_k$)를 호출할 때 수행되는 swap의 횟수를 구하라.

여러 개의 테스트 케이스가 주어진다. 첫 줄에 테스트 케이스의 수 $T$가 주어진다. 각 테스트 케이스는 다음과 같다.

첫 줄에 수열의 길이 $n$ ($1 \le n \le 10^5$)이 주어진다.

둘째 줄에 수열 $a_1, a_2, \cdots, a_n$ ($1 \le a_i \le n$)이 주어진다.

모든 테스트 케이스의 $n$을 합친 값은 $10^6$을 넘지 않는다.

각 테스트 케이스마다 $n$개의 정수 $s_1, s_2, \cdots, s_n$을 공백으로 구분하여 한 줄에 출력한다. $s_i$는 SORT($A_i$)를 호출할 때 수행되는 swap의 횟수이다.