Massiv Qurun#11668

Massiv Qurun

1 saniyə

128 meqabayt

Çətin

Əli sifirdan yeni massiv qurmağı çox xoşlayır. Bu gün o, $n$ elementdən ibarət $a_{1}, a_{2}, ..., a_{n}$ a_1, a_2, ..., a_n massivini qurmaq istəyir. Onun əlində ilkin olaraq $n$ sayda $0$ -dan ibarət $b_{1}, b_{2}, ..., b_{n}$ b_1, b_2, ..., b_n massivi var və bu massivə yalnız aşağıdakı növ əməliyyatı tətbiq edə bilər.

$M A X (l, r, x)$ MAX(l, r, x): Bu o deməkdir ki, $l \leq i \leq r$ l \le i \le r şərtini ödəyən bütün $i$ -lər üçün $b_{i} = ma x (b_{i}, x)$ b_i = max(b_i, x) olacaq. Təbii ki, bu əməliyyatda $1 \leq l \leq r \leq n$ 1 \le l \le r \le n şərti ödənməlidir.

İndi Əlini bir sual düşündürür, görəsən, minimum neçə əməliyyatla 𝑎 massivini əldə edə bilər. Əliyə minimum əməliyyat sayını və hər hansı belə əməliyyatlar ardıcıllığını tapmaqda kömək edin.

Giriş

Birinci sətirdə bir tam ədəd, $n (1 \leq n \leq 1 0^{5})$ n~(1 \le n \le 10^5), növbəti sətirdə boşluqla ayrılmış 𝑛 sayda tam ədəd, $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) verilir.

Çıxış

Çıxışa birinci sətirdə 𝑎 massivini əldə etmək üçün lazım olan minimum əməliyyat sayını verin. Bu sayı $m$ ilə işarə edək. Növbəti 𝑚 sətirdə hər hansı belə əməliyyatlar ardıcıllığını $l r x$ formatında çap edin.

Nümunələr

Nümunələr 1. Əməliyyatlar tətbiq olunduqca massivin necə dəyişdiyinə baxın:

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$ -dan daha az əməliyyatla verilmiş massivi əldə etmək mümkün deyil. Əməliyyatlar ardıcıllığının başqa düzgün versiyaları da ola bilər.

Nümunələr 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

Nümunə 1

Nümunə 2