B. Убывающую в возрастающую
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Перестановка чисел длины $$$n$$$ — это последовательность из всех целых чисел от $$$1$$$ до $$$n$$$ включительно, расположенных в определенном порядке. Другими словами, это взаимно однозначное отображение чисел от $$$1$$$ до $$$n$$$ на самих себя.

У вас есть перестановка $$$p$$$ длины $$$n$$$, отсортированная в убывающем порядке. Вы хотите отсортировать эту перестановку в возрастающем порядке. Для этого вы можете выполнять следующую операцию:

  • Выбрать два подряд идущих блока одинакогого размера и поменять их местами. Другими словами, вы выбираете два целых числа $$$(s, k)$$$ таких, что $$$1 \le s, k \le n$$$ и $$$s + 2k - 1 \le n$$$ и меняете местами блоки $$$(p_s, \ldots, p_{s+k-1})$$$ и $$$(p_{s+k}, \ldots, p_{s+2k-1})$$$.

Например, если $$$p = (2, 3, 1, 4, 5, 7, 6)$$$ и вы сделаете операцию с парой $$$s = 2$$$ и $$$k=2$$$, то вы получите перестановку $$$p = (2, 4, 5, 3, 1, 7, 6)$$$ поменяв местами подряд идущие блоки $$$(3, 1)$$$ и $$$(4, 5)$$$ длины $$$2$$$.

Отсортируйте $$$p$$$ по возрастанию используя не более $$$n$$$ операций.

Входные данные

В первой строке входного файла дано одно целое число $$$n$$$ ($$$1 \le n \le 1000$$$).

Выходные данные

В первой строке выведите одно целое число $$$m$$$ ($$$0 \le m \le n$$$) — количество сделанных вами операций.

В последующих $$$m$$$ строках выведите пары $$$(s_i, k_i)$$$ — все сделанные вами операции в порядке их выполнения.

Примеры
Входные данные
6
Выходные данные
4
1 3
1 2
2 2
3 2
Входные данные
2
Выходные данные
1
1 1
Примечание

Пояснение к первому примеру:

  1. $$$(\textbf{6, 5, 4, 3, 2, 1}) \rightarrow (3, 2, 1, 6, 5, 4)$$$
  2. $$$(\textbf{3, 2, 1, 6}, 5, 4) \rightarrow (1, 6, 3, 2, 5, 4)$$$
  3. $$$(1, \textbf{6, 3, 2, 5}, 4) \rightarrow (1, 2, 5, 6, 3, 4)$$$
  4. $$$(1, 2, \textbf{5, 6, 3, 4}) \rightarrow (1, 2, 3, 4, 5, 6)$$$