단조 ㄴㄴ

$(1, 2, \cdots, N)$의 순열 $P = (p_1, p_2, \cdots, p_N)$에 대하여 다음 조건을 만족하는 순서쌍 $(i, j, k)$의 개수를 $f(P)$라고 하자.

• $1 \leq i < j < k \leq N$.
• $p_i < p_j < p_k$ 또는 $p_i > p_j > p_k$.

$f(P)$가 최소인 순열 $P$를 출력하여라. 만약 그러한 $P$가 여러 개 존재한다면, 그 중 하나 출력한다.

입력은 다음과 같은 형식으로 주어진다.

$N$

$f(P)$가 최소인 순열 $P = (p_1, p_2, \cdots, p_N)$에 대하여 다음과 같은 형식으로 출력한다.

$p_1 \ p_2 \ \cdots \ p_N$

• $1 \le N \le 200\,000$.