Author:  Антон Карабанов  Time limit:  1 sec  
Input file:  Standard input  Memory limit:  512 Mb  
Output file:  Standard output 
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 contains natural number n.
In the first line output a nonnegative integer m — the number of ways to arrange the parentheses in the required way. In the next m lines print two spaceseparated 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 ≤ 10^{5}
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.
No.  Standard input  Standard output 

1 


2 


3 

