K. Keep Sorting
time limit per test
0.5 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

In Linear Sorting Process Computational Programming City (LSPCPC), a crucial component of the city's data systems is the Linear-Sorting Machine. This machine is designed to sort permutations of length $$$3N$$$.

A permutation of length $$$3N$$$ is an array consisting of $$$3N$$$ distinct integers from $$$1$$$ to $$$3N$$$ in arbitrary order. For example, $$$[6, 2, 5, 1, 3, 4]$$$ is a permutation of length $$$6$$$ ($$$N=2$$$), but $$$[1, 3, 3]$$$ is not a permutation.

Disaster struck when yesterday's hurricane caused severe flooding, damaging the machine's circuitry. While still operational, the machine's capabilities are now limited. It can only sort continuous segments of at most $$$2N$$$ numbers per operation.

An operation can be defined by a pair of integers $$$L$$$ and $$$R$$$, which sorts the subarray $$$A_L, A_{L+1} \ldots A_R$$$ in ascending order. As the segment can contain at most $$$2N$$$ numbers, for any operation $$$(L, R)$$$, the condition $$$R - L + 1 \le 2N$$$ must hold.

The Mayor has declared a state of emergency as the city's data arrays have become scrambled. You've been tasked with sorting a critical permutation of $$$3N$$$ integers that was being processed when the disaster hit, returning it to perfect ascending order (i.e., $$$A_i = i$$$ for all $$$1 \le i \le 3N$$$). Your goal is to find a sequence of operations to sort the permutation and determine the minimum number of sorting operations required to achieve this.

Input

The first line contains a single integer $$$N$$$ ($$$1 \le N \le 10^5$$$).

The second line contains $$$3N$$$ integers, $$$A_1, A_2, \ldots, A_{3N}$$$, representing the permutation that needs to be sorted.

Output

The first line should contain an integer $$$K$$$, representing the minimum number of operations required to sort the permutation.

The following $$$K$$$ lines should contain the sequence of operations that attain the minimum number of operations.

Each line should contain a pair of integers $$$L_i$$$ and $$$R_i$$$, representing the $$$i$$$-th operation in chronological order.

If multiple solutions achieve the minimum number of operations, you may output any one of them.

Examples
Input
2
1 4 3 2 5 6
Output
1
2 4
Input
3
1 3 2 4 5 6 7 9 8
Output
2
2 3
8 9
Note

In the first sample,

  • The original array is $$$[1, 4, 3, 2, 5, 6]$$$.
  • After applying the operation $$$(2, 4)$$$, it becomes $$$[1, 2, 3, 4, 5, 6]$$$, which is sorted in ascending order.
  • It can be proven that $$$1$$$ operation is minimal.

In the second sample,

  • The original array is $$$[1, 3, 2, 4, 5, 6, 7, 9, 8]$$$.
  • After applying the first operation $$$(2, 3)$$$, it becomes $$$[1, 2, 3, 4, 5, 6, 7, 9, 8]$$$.
  • After applying the second operation $$$(8, 9)$$$, it becomes $$$[1, 2, 3, 4, 5, 6, 7, 8, 9]$$$, which is sorted in ascending order.
  • It can be proven that $$$2$$$ operations are minimal.