나쁜 Treap

Treap은 Cartesian tree라고도 부르며, 키의 집합을 이진 탐색 트리에 저장하는 자료구조이다.

이 트리의 각 노드는 (x, y) 쌍으로 나타낸다.

노드의 x 값은 저장되는 키이다. 이진 탐색 트리 규칙을 따라서, 노드의 왼쪽 서브트리에 있는 모든 x 값은 그 노드의 x 값보다 작고, 오른쪽 서브트리에 있는 모든 x 값은 그 노드의 x 값보다 크다.

노드의 y 값은 힙 규칙을 따른다. 노드의 y 값은 부모 노드의 y 값보다 작거나 같다.

생성되는 각 노드의 y 값은 보통 어떤 분포에 따라 무작위로 고른다. 이렇게 하면 많은 연산의 평균 시간 복잡도가 좋아진다.

이름은 두 단어를 합친 말이다. TRee + hEAP = TREAP.

노드 7개인 treap, 높이는 4	샘플 테스트의 treap

Benjamin은 y 값을 고를 때 비결정성이 있으면 실행할 때마다 실행 시간이 달라지므로 나쁘다고 판단했다. 그래서 각 노드의 y 값을 x로부터 결정적으로 계산하기로 하고, 규칙 $y = \sin(x)$를 선택했다. 그는 서로 다른 정수 x는 항상 서로 다른 y를 가진다는 점을 특히 마음에 들어 한다.

Barbara는 비결정적 treap이 나쁜 난수열에서 최악의 성능을 보이고, 결정적 treap은 나쁜 키의 집합에서 최악의 성능을 보인다는 것을 안다. 그녀는 이 자료구조에 저장했을 때 높이가 n인 treap이 되는 정수 키 n개를 Benjamin에게 보여 주려 한다. 가장 불균형한 경우다.

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

서로 다른 정수 키를 한 줄에 하나씩 n줄 출력한다. 모든 키는 $-2^{31}$ 이상 $2^{31} - 1$ 이하여야 한다. 이 키들을 $y = \sin(x)$ 규칙으로 treap에 저장했을 때 높이가 n이어야 한다.