레이팅 미적용농부 존은 소들이 아침을 먹으러 목초지로 나가기 전에, 편의상 \(1 \dots N\)번으로 번호가 매겨진 \(N\)마리의 소 (\(1 \leq N \leq 10^5\))를 정렬하려 하고 있다.
현재 소들은 \(p_1, p_2, p_3, \dots, p_N\)의 순서로 한 줄로 서 있고, 농부 존은 소 \(p_1\) 앞에 서 있다. 그는 소들을 재배치하여 소 \(1\)이 농부 존 옆에 오도록 \(1, 2, 3, \dots, N\)의 순서로 만들고 싶어한다.
오늘 소들은 조금 졸린 상태라서, 어느 시점에서든 농부 존의 지시에 주의를 기울이는 소는 농부 존을 바로 마주 보고 있는 소뿐이다. 한 번의 시간 단계에서, 그는 이 소에게 줄에서 \(k\)칸 뒤로 이동하라고 지시할 수 있으며, \(k\)는 \(1\) 이상 \(N-1\) 이하의 아무 값이나 가능하다. 그 소가 지나치는 \(k\)마리의 소들은 앞으로 슬금슬금 걸어 나오고, 그 소는 그들 뒤에 끼어들 자리를 얻는다.
예를 들어 \(N=4\)이고 소들이 처음에 다음 순서로 서 있다고 하자.
FJ: 4, 3, 2, 1
농부 존에게 주의를 기울이는 소는 소 \(4\)뿐이다. 그가 소 \(4\)에게 줄에서 \(2\)칸 뒤로 이동하라고 지시하면, 순서는 다음과 같이 된다.
FJ: 3, 2, 4, 1
이제 농부 존에게 주의를 기울이는 소는 소 \(3\)뿐이므로, 두 번째 시간 단계에서 그는 소 \(3\)에게 지시를 내릴 수 있고, 이런 식으로 소들이 정렬될 때까지 계속한다.
농부 존은 정렬을 얼른 끝내고 농가로 돌아가 자신의 아침을 먹고 싶어한다. 최소 시간 단계 수로 소들을 정렬하는 지시의 순서를 찾도록 도와주자.
출제자: Dhruv Rohatgi
출제자: Dhruv Rohatgi
입력의 첫째 줄에 \(N\)이 주어진다. 둘째 줄에 소들의 시작 순서를 나타내는 \(N\)개의 정수 \(p_1, p_2, p_3, \dots, p_N\)이 공백으로 구분되어 주어진다.
첫째 줄에 소들을 정렬하는 데 필요한 최소 시간 단계 수 \(K\)를 정수 하나로 출력한다.
둘째 줄에 \(K\)개의 정수 \(c_1, c_2, \dots, c_K\)를 공백으로 구분하여 출력한다. 각 정수는 \(1 \ldots N-1\) 범위에 있어야 한다. 또한 \(i\)번째 시간 단계에서 농부 존이 자신을 마주 보는 소에게 \(c_i\)칸 뒤로 이동하라고 지시했을 때, \(K\)번의 시간 단계 후 소들이 정렬된 순서가 되어야 한다.
최적의 지시 순서가 여러 개 있으면 그중 아무것이나 출력해도 된다.
sleepy.in · 출력을 쓸 파일 sleepy.out4
1 2 4 33
2 2 3