Number Game

Time limit2sMemory limit1024 MB

Summary

Given 1 to N on a board, repeatedly replace two numbers with their absolute difference. Maximize the final number and print the operations.

Level: Medium6 of 10
Topics: Math, Greedy, Implementation
Solved: No attempts yet

Problem

A board has the $N$ distinct integers $1$ through $N$ . Repeat the following until only one integer remains on the board.

Choose two integers on the board, erase them, and write the absolute difference of the two numbers.

For example, with $1,2,3,4$ on the board, choosing $1$ and $4$ leaves $2,3,3$ . Then choosing the two $3$ s leaves $2,0$ .

What must be done to make the final remaining integer as large as possible?

Input

The first line contains an integer $N$ . ( $2\le N\le 200\, 000$ )

Output

On the first line, print the largest integer that can remain at the end.

Then print $N-1$ lines. For every $1 \le i \le N-1$ , the $(i+1)$ -th line contains the two integers chosen in the $i$ -th operation, separated by a space.

Examples1

Example 1
Input
```
2
```
Expected output
```
1
2 1
```