include

include

// Merge and count inversions long long mergeAndCount(int arr[], int temp[], int left, int mid, int right) { long long inv_count = 0; int i = left; int j = mid; int k = left;

while (i <= mid - 1 && j <= right) {
    if (arr[i] <= arr[j]) {
        temp[k++] = arr[i++];
    } else {
        temp[k++] = arr[j++];
        inv_count += (mid - i);
    }
}

while (i <= mid - 1)
    temp[k++] = arr[i++];

while (j <= right)
    temp[k++] = arr[j++];

for (i = left; i <= right; i++)
    arr[i] = temp[i];

return inv_count;

}

// Merge sort with inversion count long long mergeSortAndCount(int arr[], int temp[], int left, int right) { long long inv_count = 0; if (left < right) { int mid = (left + right) / 2;

    inv_count += mergeSortAndCount(arr, temp, left, mid);
    inv_count += mergeSortAndCount(arr, temp, mid + 1, right);
    inv_count += mergeAndCount(arr, temp, left, mid + 1, right);
}
return inv_count;

}

int main() { int t; scanf("%d", &t);

while (t--) {
    int n;
    scanf("%d", &n);

    int* arr = (int*)malloc(n * sizeof(int));
    int* temp = (int*)malloc(n * sizeof(int));

    for (int i = 0; i < n; i++)
        scanf("%d", &arr[i]);

    long long result = mergeSortAndCount(arr, temp, 0, n - 1);
    printf("%lld\n", result);

    free(arr);
    free(temp);
}

return 0;

}