Reversal Sorting

You have an array that contains a permutation of integers 1,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 n reversals.

Input

The first input line has an integer n: the size of the array. The array elements are numbered 1,2,\dots,n. The next line has n integers x_1,x_2,\dots,x_n: the contents of the array.

Output

First print an integer k: the number of reversals. After that, print k lines that describe the reversals. Each line has two integers a and b: you reverse a subarray from position a to position b.

Constraints

$1 \le n \le 2$ \cdot 10^5$

Example

Input

4
2 3 1 4

Output

2
1 3
2 3