B. From decreasing to increasing
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

A permutation of length $$$n$$$ is a sequence of all integers from $$$1$$$ to $$$n$$$ inclusive, arranged in a certain order. In other words, it is a one-to-one mapping of numbers from $$$1$$$ to $$$n$$$ onto themselves.

You have a permutation $$$p$$$ of length $$$n$$$, sorted in decreasing order. You want to sort this permutation in increasing order. To do this, you can perform the following operation:

  • Choose two consecutive blocks of the same size and swap them. In other words, you choose two integers $$$(s, k)$$$ such that $$$1 \le s, k \le n$$$ and $$$s + 2k - 1 \le n$$$, and swap the blocks $$$(p_s, \ldots, p_{s+k-1})$$$ and $$$(p_{s+k}, \ldots, p_{s+2k-1})$$$.

For example, if $$$p = (2, 3, 1, 4, 5, 7, 6)$$$ and you perform the operation with the pair $$$s = 2$$$ and $$$k=2$$$, you will get the permutation $$$p = (2, 4, 5, 3, 1, 7, 6)$$$ by swapping the consecutive blocks $$$(3, 1)$$$ and $$$(4, 5)$$$ of length $$$2$$$.

Sort $$$p$$$ in increasing order using no more than $$$n$$$ operations.

Input

The first line of the input file contains a single integer $$$n$$$ ($$$1 \le n \le 1000$$$).

Output

In the first line, output a single integer $$$m$$$ ($$$0 \le m \le n$$$) — the number of operations you performed.

In the next $$$m$$$ lines, output pairs $$$(s_i, k_i)$$$ — all the operations you performed in the order they were performed.

Examples
Input
6
Output
4
1 3
1 2
2 2
3 2
Input
2
Output
1
1 1
Note

Explanation for the first example:

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