대안 순열

Johnny는 순열을 이진 탐색 트리(BST)로 바꾸는 변환기를 작성했다. 순열 $(\pi_1, \pi_2, \ldots, \pi_n)$이 주어지면 $\pi_1$을 루트에 놓는다. $(\pi_2, \pi_3, \ldots, \pi_n)$ 가운데 $\pi_1$보다 작은 수들은 원래 순서를 유지한 채 재귀적으로 BST를 만들고, 이를 루트의 왼쪽 서브트리로 붙인다. 대칭적으로, $\pi_1$보다 큰 수들로 BST를 만들어 오른쪽 서브트리로 붙인다. Johnny는 놀랍게도 서로 다른 순열이 같은 BST를 만들 수 있다는 사실을 발견했다. 예를 들어 $(2, 3, 1)$과 $(2, 1, 3)$은 같은 BST를 만든다. 이 사실에 놀란 그는 Johnny's Numbers $J_k$를 정의했다. $k$번째 Johnny's Number $J_k$는 $1, 2, \ldots, n$의 순열 정확히 $k$개로부터 얻을 수 있는, 레이블이 $1, 2, \ldots, n$인 $n$개 노드의 BST가 존재하는 가장 작은 $n$이다. Johnny's Numbers를 연구하기는 어렵고, 이에 대한 관심도 줄고 있다. 주어진 $k$에 대해 $J_k$를 계산하도록 Johnny를 도와라.

첫 줄에 자연수 $k$ ($1 \le k \le 10^{11}$)가 주어진다.

첫 줄에 양의 정수 $J_k$를 출력한다. 단, $J_k$가 존재하고 $5000$ 이하일 때만 출력한다. 둘째 줄에는 $k$개의 생성 순열 가운데 사전순으로 가장 작은 것을 이루는 $J_k$개의 정수를 출력한다. 그렇지 않으면, 즉 $J_k$가 존재하지 않거나 $5000$보다 크면 NIE를 출력한다. (NIE는 폴란드어로 '아니오'라는 뜻이다.)

생성 순열이 정확히 여덟 개인 트리는 아래 그림과 같다: 이 트리를 생성하는 순열은 모두 다음과 같다: $(2, 1, 4, 3, 5)$, $(2, 1, 4, 5, 3)$, $(2, 4, 1, 3, 5)$, $(2, 4, 1, 5, 3)$, $(2, 4, 3, 1, 5)$, $(2, 4, 3, 5, 1)$, $(2, 4, 5, 1, 3)$, $(2, 4, 5, 3, 1)$.