Create an array

Ali loves to create a new array from scratch. Today, he wants to build an array $a_1,a_2,...,a_n$ of $n$ elements. Initially, he has an array $b_1,b_2,...,b_n$ containing $n$ zeros, and he can only apply the following operations to this array:

• $MAX(l,r,x)$: This means that $b_i=\max (b_i,x)$ for all $i$ satisfying the condition $l\le i\le r$. Of course, in this operation, the condition $1\le l\le r\le n$ must be satisfied.

Now Ali is thinking about the minimum number of operations he can perform to obtain the array $a$. Help Ali find the minimum number of operations and any sequence of such operations.

Input

The first line contains a single integer $n(1\le n\le 10^5)$. The next line contains $n$ integers $a_1,a_2,...,a_n(0\le a_i\le 10^9)$.

Output

Output the minimum number of operations required to obtain the array 𝑎 in the first line. Denote this number by $m$. Output any sequence of operations in the following $m$ lines in the format $lrx$.

Examples

Example 1. See how the array changes as operations are applied:

b[] = 0 0 0 0 0 0 0 0
b[] = 1 1 1 0 0 0 0 0
b[] = 1 7 1 0 0 0 0 0
b[] = 1 7 1 7 7 0 0 0
b[] = 1 7 1 7 7 2 2 2
b[] = 1 7 1 7 7 3 2 2
b[] = 1 7 1 7 7 3 2 3

It's impossible to obtain the given array in fewer than $6$ operations. There may be other correct sequences of operations.

Example 2.

b[] = 0 0 0 0 0 0 0
b[] = 0 0 1 1 1 1 0
b[] = 0 0 1 3 3 1 0