2019 ICPC Asia Danang Regional Contest


2019-12-05 16:20 AKST

2019 ICPC Asia Danang Regional Contest


2019-12-05 21:20 AKST
The end is near!
Contest is over.
Not yet started.
Contest is starting in -518 days 3:08:52

Time elapsed


Time remaining


Problem K
Keep It Sorted

Gon has a permutation $a = (a_1, a_2, \ldots , a_ n)$ of integers between $1$ and $n$ (inclusive), and wants to sort it in increasing order. However, sorting is trivial — anyone can sort an array!

Thus, Gon decides to only use the following operation to sort:

  • Select $2$ indices $\ell $ and $r$ $(1 \leq \ell \leq r \leq n)$, such that the sub-array $(a_{\ell }, a_{\ell +1}, \ldots , a_{r})$ is sorted, in either increasing or decreasing order.

  • Reverse the sub-array from $\ell $ to $r$.

For example, given a permutation $a = (3, 2, 1)$, Gon can sort it with $1$ operation as follow:

  • Select $\ell = 1, r = 3$.

  • Reverse the sub-array $(a_1, a_2, a_3)$ to get $a = (1, 2, 3)$.

Note that if $a = (3, 1, 2)$, Gon cannot select $\ell = 1, r = 3$, as the sub-array from $1$ to $3$ is not sorted.

As Gon’s birthday is Jan 19th, Gon wants to use at most $191$ operations. This turns out to be non-trivial. Please help Gon!


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

The second line of input contains $n$ integer $a_1, a_2, \ldots , a_ n$. It is guaranteed that $a$ is a permutation of integers between $1$ and $n$, inclusive.


Print a single number $k$ $(0 \le k \le 191)$ on the first line — the number of operations you want to use.

In each of the next $k$ lines, print two integers $\ell $ and $r$ $(1 \le \ell \le r \le n)$ describing the operations. The sub-array between $\ell $ and $r$ must be sorted before this operation.

After $k$ operations, the permutation $a$ must be sorted in increasing order. In other words, $a_ i = i$ for every valid index $i$. Note that you do not need to minimize the number of operations.

It is guaranteed that a solution exists. If there are multiple solutions, you can print any of them.

Sample Input 1 Sample Output 1
3 1 2
1 1
2 2
3 3
1 2
2 3
1 3
1 3