숫자 놀이

시간 제한2초메모리 제한1024 MB

요약

칠판에 적힌 1부터 N까지의 정수에서 두 수를 골라 차를 적는 과정을 반복할 때, 마지막에 남는 수를 가장 크게 만드는 방법을 찾고 그 순서를 출력한다.

문제

칠판에 $1$ 부터 $N$ 까지 $N$ 개의 서로 다른 정수를 적고, 칠판에 정수가 하나만 남을 때까지 다음을 반복한다.

예를 들어, $1,2,3,4$ 가 적혀 있을 때 $1$ 과 $4$ 를 선택하면 칠판에는 $2,3,3$ 이 적혀 있게 되고, 그다음 두 개의 $3$ 을 선택하면 $2,0$ 이 적혀 있게 된다.

마지막에 남는 정수를 가장 크게 하려면 어떻게 해야 할까?

첫 번째 줄에 정수 $N$ 이 주어진다. ( $2\le N\le 200\\, 000$ )

첫 번째 줄에는 마지막에 남을 수 있는 가장 큰 정수를 출력한다.

그다음 $N-1$ 개의 줄에 걸쳐서 그 정수를 남기는 방법을 출력한다. 모든 $1 \leq i \leq N-1$ 에 대해, $i+1$ 번째 줄에는 $i$ 번째로 선택한 두 정수를 공백으로 구분하여 출력한다.