삽입 순서

한 친구가 알고리즘과 자료 구조 수업을 듣고 있다. 지난주에 이진 검색 트리를 배우면서, 트리 높이를 낮게 유지해 모든 노드에 빠르게 접근하려면 자기 균형 트리를 써야 한다는 점도 함께 배웠다.

이진 검색 트리는 각 노드가 키를 저장하는 이진 트리이며, 각 노드의 키는 왼쪽 부분 트리에 있는 모든 키보다 크고 오른쪽 부분 트리에 있는 모든 키보다 작다는 성질을 만족한다. 새 키를 삽입할 때는 이 성질이 유지되는 유일한 위치에 그 키를 가진 새로운 리프 노드를 추가한다. 아래 그림을 참고하라.

그림 I.1: 첫 번째 예제의 삽입 과정.

자기 균형 없이 트리가 얼마나 나빠질 수 있는지 보여 주려고 한다. 삽입 순서를 잘 고르면 거의 어떤 높이의 트리도 만들 수 있음을 친구에게 알려 주려는 것이다.

두 정수 n과 k가 주어지면, 노드가 n개이고 높이가 k인 이진 검색 트리를 만들려고 한다. 여기서 트리의 높이는 루트에서 리프까지의 경로에 있는 노드 개수의 최댓값이다. 이를 위해 정수 1부터 n까지의 순열을 하나 찾아야 한다. 이 순열의 순서대로 빈 이진 검색 트리에 삽입했을 때(자기 균형 없이) 만들어지는 트리의 높이가 k여야 한다.

입력은 두 정수 n과 k로 이루어진다. (1 ≤ k ≤ n ≤ 2 · 105) n은 트리의 노드 개수이고 k는 트리가 가져야 하는 정확한 높이이다.

해가 없으면 impossible을 출력한다. 그렇지 않으면 요구되는 순열의 n개 정수를 한 줄에 출력한다. 해가 여러 개라면 그중 아무거나 출력해도 된다.