## Problem K. Keep on doing! ≡

• problems
• en ru
 Author: Антон Карабанов Time limit: 1 sec Input file: Standard input Memory limit: 512 Mb Output file: Standard output

### Statement

The expression n − (n − 1) − (n − 2) − (n − 3) − ...  − 3 − 2 − 1 is written on the board (for example, if n = 5 it will be written as 5 − 4 − 3 − 2 − 1). To avoid a failing grade in mathematics, Gavrila needs to put left and right parentheses in this expression, so that the result is zero. How many ways does he have to do it?

### Input format

Input contains natural number n.

### Output format

In the first line output a non-negative integer m — the number of ways to arrange the parentheses in the required way. In the next m lines print two space-separated natural numbers a and b — the position of the parentheses (numbers from a to b inclusive will be inside the brackets). Output numbers a and b in descending order, and output pairs of numbers in order of descending a.

4 ≤ n ≤ 105

### Note on samples

In the first example, n = 5 is given. Unfortunately, Gavrila won't succeed, for the given n there is no way to place the brackets in the required way.

In the second example n = 7 is given. If all numbers from 5 to 3 are enclosed in brackets, then an expression with the desired value will be obtained: 7 − 6 − (5 − 4 − 3) − 2 − 1 = 1 − ( − 2) − 3 = 0.

In the third example, for n = 12 there are several ways to solve the problem.

### Sample tests

No. Standard input Standard output
1
5
0
2
7
1
5 3
3
12
2
11 8
8 2

0.073s 0.007s 13