Побудуйте масив#11668

Побудуйте масив

1 секунда

128 мегабайтів

Складна

Алі з нуля любить створювати новий масив. Сьогодні він хоче побудувати масив $a_{1}, a_{2}, ..., a_{n}$ a_1, a_2, ..., a_n з $n$ елементів. Спочатку у нього є масив $b_{1}, b_{2}, ..., b_{n}$ b_1, b_2, ..., b_n, який містить $n$ нулів, і він може застосовувати до цього масиву лише наступні операції:

$M A X (l, r, x)$ MAX(l, r, x): Це означає, що $b_{i} = ma x (b_{i}, x)$ b_i = max(b_i, x) для всіх $i$ , що задовольняють умові $l \leq i \leq r$ l \le i \le r. Звісно, у цій операції повинна виконуватися умова $1 \leq l \leq r \leq n$ 1 \le l \le r \le n.

Тепер Алі думає над тим, за яке мінімальне число операцій він зможе отримати масив $a$ . Допоможіть Алі знайти мінімальну кількість операцій і будь-яку послідовність таких операцій.

Вхідні дані

Перший рядок містить одне ціле число $n (1 \leq n \leq 1 0^{5})$ n~(1 \le n \le 10^5). Наступний рядок містить $n$ цілих чисел $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).

Вихідні дані

Виведіть мінімальну кількість операцій, необхідну для отримання масиву $a$ у першому рядку. Позначимо це число через $m$ . Виведіть будь-яку таку послідовність операцій у наступних $m$ рядках у форматі $l r x$ .

Приклади

Приклад 1. Подивіться, як змінюється масив у міру застосування операцій:

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++

Неможливо отримати даний масив менш ніж за $6$ операцій. Можуть бути й інші правильні варіанти послідовності операцій.

Приклад 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

Приклад 1

Приклад 2