정렬

유전 프로그래밍(Genetic Programming)은 컴퓨터 프로그램을 자동으로 만들어 내는 기법입니다. 유전 프로그래밍 알고리즘은 주어진 입력에 대해 원하는 결과를 내놓는 프로그램을 찾으려고 시도합니다. 이는 진화적(evolutionary) 기법으로, 생물학적 진화를 본뜬 인공 진화를 통해 알맞은 프로그램을 탐색합니다.

유전 프로그래밍으로 아래에 C 언어로 제시된 정수 정렬 알고리즘 sort() 가 만들어졌습니다. 이 알고리즘은 올바르게 동작하며, 수들을 큰 값에서 작은 값 순서로 정렬합니다. sort() 의 가장 안쪽 반복문에서는 보조 프로시저 swap() 이 호출됩니다. 주어진 배열 $t$ 에 대해 swap() 이 몇 번 실행되는지 빠르게 셀 수 있겠습니까?

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]);
}

첫째 줄에 테스트의 개수를 나타내는 자연수 $d$ ($1 \le d \le 100$) 가 주어집니다.

각 테스트의 첫째 줄에는 배열 $t$ 의 크기 $n$ ($1 \le n \le 10^5$) 이 주어집니다. 둘째 줄에는 배열 $t$ 의 원소 $n$ 개가 주어지며, 각 원소는 $-10^9 \le t_i \le 10^9$ 를 만족합니다 ($i = 1 \dots n$).

각 테스트마다 swap() 프로시저가 호출된 횟수를 한 줄에 하나씩 출력합니다.