CSES - Reversal Sorting
  • Time limit: 1.00 s
  • Memory limit: 512 MB

You have an array that contains a permutation of integers 1,2,,n1,2,\dots,n. Your task is to sort the array in increasing order by reversing subarrays. You can construct any solution that has at most nn reversals.

Input

The first input line has an integer nn: the size of the array. The array elements are numbered 1,2,,n1,2,\dots,n.

The next line has nn integers x1,x2,,xnx_1,x_2,\dots,x_n: the contents of the array.

Output

First print an integer kk: the number of reversals.

After that, print kk lines that describe the reversals. Each line has two integers aa and bb: you reverse a subarray from position aa to position bb.

Constraints

  • 1n21051 \le n \le 2 \cdot 10^5

Example

Input:

4
2 3 1 4

Output:

2
1 3
2 3