Задача 38. Разность ≡

Условие

...

В безмерной разности теряться

И благодарны слезы лить.

Гавриил Державин, "Бог", 1784 г.

Корень учения горек, зато плод его сладок — с первой частью этой пословицы второклассник Гаврила полностью согласен, а до второй пока не дорос. Судите сами: по закону Божьему — двойка, по чтению и письму — кол, по арифметике... ну тут ещё есть шанс избежать досрочного исключения из главного народного училища. Если решит пример, конечно.

На доске записано числовое выражение 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 ≤ 10⁵

Система оценки и описание подзадач

Баллы за каждый тест начисляются независимо.

Пояснение к примерам

В первом примере дано n = 5. К сожалению, у Гаврилы ничего не выйдет, для данного n нет возможности расставить скобки требуемым образом.

Во втором примере дано n = 7. Если все числа от 5 до 3 заключить в скобки, то получится выражение с нужным значением: 7 − 6 − (5 − 4 − 3) − 2 − 1 = 1 − ( − 2) − 3 = 0.

В третьем примере для n = 12 есть несколько способов решить задачу и продолжить обучение.

Примеры тестов

5

0

7

1
5 3

12

2
11 8
8 2