| 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 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
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 | |
|