칵테일 셰이커 정렬

칵테일 셰이커 정렬은 버블 정렬을 변형한 방법이다. 버블 정렬과 달리 수열의 양쪽 끝을 번갈아 가며 정리한다.

$1$부터 $N$까지의 정수가 한 번씩 들어 있는 길이 $N$의 수열이 주어진다. 칵테일 셰이커 정렬은 다음 순서로 진행한다.

1. 수 $1$을 이웃한 수와 한 번씩 교환해 첫 번째 자리까지 옮긴다.
2. 수 $N$을 같은 방식으로 마지막 자리까지 옮긴다.
3. 수 $2$를 두 번째 자리까지 옮긴다.
4. 수 $N-1$을 $N-1$번째 자리까지 옮긴다.
5. 이런 식으로 $N$번째 단계까지 계속한다.

예를 들어 $N = 6$이고 처음 수열이 654321이라고 하자. 첫 번째 단계에서 수 1이 5번 교환되어 수열은 165432가 된다. 두 번째 단계에서 수 6이 4번 교환되어 154326이 된다. 세 번째 단계에서 수 2가 3번 교환되어 125436이 된다. 네 번째 단계에서 수 5가 2번 교환되어 124356이 된다. 다섯 번째 단계에서 수 3이 1번 교환되어 123456이 된다. 여섯 번째 단계에서는 수 4가 이미 네 번째 자리에 있으므로 교환이 일어나지 않는다.

칵테일 셰이커 정렬의 각 단계에서 일어나는 교환 횟수를 세는 프로그램을 작성한다.

첫째 줄에 테스트 케이스의 개수 $T$가 주어진다. ($1 \le T \le 15$) 다음으로 테스트 케이스가 아래 형식으로 이어진다.

각 테스트 케이스의 첫째 줄에는 양의 정수 $N$이 주어진다. ($1 \le N \le 100000$)

둘째 줄에는 $1$부터 $N$까지의 서로 다른 정수 $N$개가 공백 하나로 구분되어 주어진다.

$T$개의 줄을 출력한다. 각 테스트 케이스마다 $N$개 단계의 교환 횟수를 단계 순서대로 공백 하나로 구분해 한 줄에 출력한다.

$N = 5$이고 수열이 2 4 1 5 3인 경우를 보자. 첫 번째 단계에서 수 1이 2번 교환되어 수열은 12453이 된다. 두 번째 단계에서 수 5가 1번 교환되어 12435가 된다. 세 번째 단계에서는 수 2가 이미 두 번째 자리에 있으므로 교환이 0번 일어난다. 네 번째 단계에서 수 4가 1번 교환되어 12345가 된다. 다섯 번째 단계에서도 교환이 0번 일어난다.