스왑

$1$부터 $n$까지의 정수가 한 번씩 나타나는 길이 $n$의 수열 $x_1, x_2, \dots, x_n$이 주어진다.

두 수를 바꾸는 "스왑" 연산으로 이 수열을 고칠 수 있다. $k = 2, 3, \dots, n$ 순서로 $k$를 하나씩 늘려 가면서, 각 $k$마다 $x_k$와 $x_{\lfloor k/2 \rfloor}$를 바꿀지 바꾸지 않을지 고를 수 있다. 이미 지나간 $k$로는 돌아가지 못한다.

수열 $a_1, a_2, \dots, a_n$이 수열 $b_1, b_2, \dots, b_n$보다 사전순으로 앞선다는 것은, $k < j$인 모든 $k$에 대해 $a_k = b_k$이고 $a_j < b_j$인 $j$ $(1 \le j \le n)$가 존재한다는 뜻이다.

순서대로 "스왑" 연산을 골라 만들 수 있는 수열 중 사전순으로 가장 앞선 수열은 무엇일까?

첫 줄에 정수 $n$이 주어진다. $(1 \le n \le 5000)$

둘째 줄에 수열을 이루는 $n$개의 정수가 공백으로 구분되어 주어진다. 이 수열은 $1$부터 $n$까지의 정수를 한 번씩 담은 순열이다.

첫 줄에 순서대로 "스왑" 연산을 골라 만들 수 있는 수열 중 사전순으로 가장 앞선 수열을 나타내는 $n$개의 정수를 공백으로 구분해 출력한다.