405441: GYM101962 M Sorting Machine

Betinho, the mayor of Soteropolis, striked (the public coffers) again! Now he bought a Sorting Machine.

A Sorting Machine is a dedicated processor with 1000 cores and a shared memory capable of storing an array of integers. In one operation, one can select up to 1000 disjoint intervals of this array and sort them concurrently. The cost of such operation is the maximum between the costs of sorting each of these intervals independently.

The cost of sorting a single interval is $$$L \lceil \log_2(K + 1) \rceil$$$, where $$$L$$$ is the size of the interval and $$$K$$$ is the number of adjacent inversions it has. An adjacent inversion is a valid index $$$i$$$ such that $$$a_i > a_{i+1}$$$.

Netinho wants to use his machine to sort the sequence $$$n, n-1, n-2, \dots, 2, 1$$$. He wants to do at most 10 operations to sort this sequence, and he wants the total cost to be no more than $$$7n$$$. Find him a valid sequence of operations.

The first line contains a single integer $$$n$$$ ($$$4 \leq n \leq 10^5$$$).

The first line should contain the number of operations $$$O$$$ to be executed.

Then there should be $$$O$$$ blocks describing each operation.

A operation block should contain in its first line an integer $$$K$$$ ($$$1 \leq K \leq min(n, 1000)$$$) – the number of disjoint intervals used in this operation.

The next $$$K$$$ lines of the block should contain two integers $$$L, R$$$ ($$$1 \leq L \leq R \leq n$$$) – the boundaries of the interval to be sorted.

4

2
2
1 2
3 4
1
1 4

5

3
3
1 2
3 4
5 5
2
1 4
5 5
1
1 5