Create an array#11668

Create an array

1 second

128 megabytes

Hard

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

$M A X (l, r, x)$ MAX(l, r, x): This means that $b_{i} = ma x (b_{i}, x)$ b_i = max(b_i, x) for all $i$ satisfying the condition $l \leq i \leq r$ l \le i \le r. Of course, in this operation, the condition $1 \leq l \leq r \leq n$ 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 \leq n \leq 1 0^{5})$ n~(1 \le n \le 10^5). The next line contains $n$ integers $a_{1}, a_{2}, ..., a_{n} (0 \leq a_{i} \leq 1 0^{9})$ 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 $a$ in the first line. Denote this number by $m$ . Output any sequence of operations in the following $m$ lines in the format $l r x$ .

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

C++

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

Example 1

Example 2