As a master of sorting, you are often challenged by passing tourists who ask you to sort sequences using strange operations.

Because you are a world-renowned sorting master, a novice sorter from a neighboring country, Little I, has come to visit you. He left behind a permutation $a_1, a_2, \cdots, a_n$ of length $n$ and asked you to sort it in ascending order using the following operation:

• Define $a_{i \sim j} = \{a_i, a_{i+1}, \cdots, a_j\}$. Select $1 \le i \le j < k \le l \le n$ and swap the segments $a_{i \sim j}$ and $a_{k \sim l}$. That is, after the swap, the sequence becomes $a_{1 \sim i-1}, a_{k \sim l}, a_{j+1 \sim k-1}, a_{i \sim j}, a_{l+1 \sim n}$.

Since you are a sorting master famous for your pursuit of perfection, you need to provide a sorting scheme that minimizes the number of operations.

Input

The first line contains an integer $n$ ($1 \le n \le 2,000$), representing the length of the sequence. The second line contains $n$ integers $a_1, a_2, \cdots, a_n$ ($1 \le a_i \le n$), describing the permutation.

Output

The first line contains an integer $s$, representing the number of steps in your scheme. The following $s$ lines each contain four integers $i, j, k, l$, representing one operation. If there are multiple solutions, you may output any one of them.

Examples

Input 1

6
1 4 5 3 2 6

Output 1

1
2 3 5 5

Note 1

Selecting $i = 2, j = 3, k = 5, l = 5$, the sequence $1\;{\color{blue}{4\;5}}\;3\;{\color{red}{2}}\;6$ becomes $1\;{\color{red}{2}}\;3\;{\color{blue}{4\;5}}\;6$.