레이팅 미적용설명
Frane는 수의 배열을 정렬하는 일을 맡았다. 배열은 \(1\) 이상 \(N\) 이하의 정수 \(N\)개로 이루어지며, 각 수는 배열에 정확히 한 번씩 나타난다. Frane는 \(N\)개의 단계로 동작하는 다음 정렬 알고리즘을 생각해 내고 터보소트(turbosort)라고 이름 붙였다:
- 첫 번째 단계에서는 인접한 원소들을 반복해서 교환하여 수 \(1\)을 위치 \(1\)로 옮긴다.
- 두 번째 단계에서는 같은 방법으로 수 \(N\)을 위치 \(N\)으로 옮긴다.
- 세 번째 단계에서는 수 \(2\)를 위치 \(2\)로 옮긴다.
- 네 번째 단계에서는 수 \(N-1\)을 위치 \(N-1\)로 옮긴다.
- 이런 식으로 계속한다.
다시 말해, 단계의 번호가 홀수이면 Frane는 아직 고르지 않은 수 중 가장 작은 수를 골라 최종 위치로 옮기고, 짝수 단계에서는 아직 고르지 않은 수 중 가장 큰 수를 고른다.
초기 배열이 주어졌을 때, 알고리즘의 각 단계에서 일어나는 교환의 횟수를 출력하는 프로그램을 작성하시오.
제약
입력 형식
첫째 줄에 배열의 원소 개수인 정수 \(N\) (\(1 \le N \le 100\,000\))이 주어진다.
다음 \(N\)개의 줄에는 \(1\) 이상 \(N\) 이하의 정수가 하나씩 주어진다. 정렬할 배열이다. 배열에 중복은 없다.
출력 형식
\(N\)개의 각 단계에 대해, 교환 횟수를 한 줄에 하나씩 출력한다.
채점: 전체 점수의 \(70\%\)에 해당하는 테스트 케이스에서는 \(N\)이 \(100\)보다 작다.
서브태스크
| 서브태스크 | 점수 | 설명 |
|---|---|---|
Subtask 1 | 70점 |
예제 1
입력
3
2
1
3출력
1
0
0예제 2
입력
5
5
4
3
2
1출력
4
3
2
1
0예제 3
입력
7
5
4
3
7
1
2
6출력
4
2
3
0
2
1
0문제 정보
태그