| Автор: | Антон Карабанов | Ограничение времени: | 1 сек | |
| Входной файл: | Стандартный вход | Ограничение памяти: | 512 Мб | |
| Выходной файл: | Стандартный выход |
На доске записано выражение n − (n − 1) − (n − 2) − (n − 3) − ... − 3 − 2 − 1 (например, при n = 5 будет написано 5 − 4 − 3 − 2 − 1). Чтобы избежать двойки по математике, Гавриле требуется поставить в этом выражении левую и правую скобки, так, чтобы в результате получился ноль. Сколько у него есть способов это сделать?
Входные данные содержат натуральное число n.
Выведите в первой строке неотрицательное целое число m — количество способов расставить скобки требуемым образом. В следующих m строках через пробел выведите два натуральных числа a и b — положение скобок (числа от a до b включительно окажутся внутри скобок). Числа a и b выводите в порядке убывания, а пары чисел выводите в порядке убывания a.
4 ≤ n ≤ 105
В первом примере дано n = 5. К сожалению, у Гаврилы ничего не выйдет, для данного n нет возможности расставить скобки требуемым образом.
Во втором примере дано n = 7. Если все числа от 5 до 3 заключить в скобки, то получится выражение с нужным значением: 7 − 6 − (5 − 4 − 3) − 2 − 1 = 1 − ( − 2) − 3 = 0.
В третьем примере для n = 12 есть несколько способов решить задачу.
| № | Стандартный вход | Стандартный выход |
|---|---|---|
| 1 | |
|
| 2 | |
|
| 3 | |
|