터보소트

터보소트는 1부터 N까지의 정수가 한 번씩 섞여 있는 배열에만 적용되는 정렬 과정이다.

과정은 총 N단계로 진행된다. 아직 선택되지 않은 수들만 남아 있다고 생각하며, 단계마다 다음 수를 하나 고른다.

• 홀수 번째 단계에서는 아직 선택되지 않은 수 중 가장 작은 수를 고른다. 그 수를 인접한 수와 계속 바꾸어, 아직 정해지지 않은 구간의 가장 왼쪽 자리로 보낸다.
• 짝수 번째 단계에서는 아직 선택되지 않은 수 중 가장 큰 수를 고른다. 그 수를 인접한 수와 계속 바꾸어, 아직 정해지지 않은 구간의 가장 오른쪽 자리로 보낸다.

각 단계에서 실제로 필요한 인접 교환 횟수를 구해야 한다.

1부터 N까지의 수로 이루어진 배열이 주어질 때, 터보소트의 각 단계에서 몇 번의 인접 교환이 일어나는지 출력하라.

첫째 줄에 배열의 크기 N이 주어진다. N은 1 이상 100,000 이하의 자연수이다.

둘째 줄부터 N개의 줄에는 배열에 들어 있는 수가 앞에서부터 차례대로 하나씩 주어진다. 각 수는 1 이상 N 이하이며, 같은 수는 두 번 나오지 않는다.

총 N줄을 출력한다. i번째 줄에는 터보소트의 i번째 단계에서 필요한 인접 교환 횟수를 출력한다.