Sizə sehrli çubuqdan ibarət bir massiv verilir, burada -ci çubuğun uzunluğu a_i-dir. Biz massivini yaxşı adlandırırıq, əgər (1 \le i < j < k \le |b|) tripletini tapmaq mümkündürsə, belə ki, b_i, b_j və b_k tərəfləri ilə qeyri-dejenerat üçbucaq mövcuddur.
Sizdən iki növ sorğunu idarə etməyiniz xahiş olunur:
— -ci mövqedəki sehrli çubuğun uzunluğu -ə dəyişdi;
— massivini yaxşı olan hissələrə bölmək üçün maksimum qeyri-boş ardıcıl alt-seqmentlərin sayını çap edin. Hər bir elementin yaxşı alt-seqmentə aid olmasını unutmayın. Əgər seqment qeyri-boş ardıcıl alt-seqmentlərə bölünə bilmirsə, cavab -dır.
Girişin birinci sətrində iki tam ədəd və (1 \le n,q \le 5 \cdot 10^5) verilir — sehrli çubuqların massivinin uzunluğu və sorğuların sayı.
Girişin ikinci sətrində tam ədəd a_i (1 \le a_i \le 10^6) verilir — massivindəki sehrli çubuqların uzunluqları.
Aşağıdakı sətrinin hər biri aşağıdakı növ sorğulardan birini ehtiva edir:
(1 \le i \le n, 1 \le x \le 10^6);
(1 \le l \le r \le n).
Hər növ sorğu üçün bir sətirdə bir tam ədəd çap edin — seqmenti yaxşı olan qeyri-boş ardıcıl alt-seqmentlərə bölmək üçün maksimum say. Əgər seqment qeyri-boş ardıcıl alt-seqmentlərə bölünə bilmirsə, çap edin.
Example 1
İlk massiv a = [1, 3, 5, 4, 7, 5, 4, 3, 9, 8]-dir.
Sorğu "2 1 10": Biz bütün massivi yaxşı alt-seqmentə bölə bilərik: [1, 3, 5, 4], [7, 5, 4], [3, 9, 8].
[1, 3, 5, 4] yaxşıdır: , , uzunluğunda çubuqlar bir üçbucaq yaradır (3 + 4 > 5).
[7, 5, 4] yaxşıdır: , , uzunluğunda çubuqlar bir üçbucaq yaradır (4 + 5 > 7).
[3, 9, 8] yaxşıdır: , , uzunluğunda çubuqlar bir üçbucaq yaradır (3 + 8 > 9).
Sorğu "1 3 3": Massiv a = [1, 3, 3, 4, 7, 5, 4, 3, 9, 8] olur.
Sorğu "2 1 10": Biz bütün massivi yaxşı alt-seqmentə bölə bilərik: [1, 3, 3], [4, 7, 5], [4, 3, 9, 8].
[1, 3, 3] yaxşıdır: , , uzunluğunda çubuqlar bir üçbucaq yaradır (1 + 3 > 3).
[4, 7, 5] yaxşıdır: , , uzunluğunda çubuqlar bir üçbucaq yaradır (4 + 5 > 7).
[4, 3, 9, 8] yaxşıdır: , , uzunluğunda çubuqlar bir üçbucaq yaradır (4 + 8 > 9).
Sorğu "2 1 7": Alt-massiv [1, 3, 3, 4, 7, 5, 4]-dir. Biz onu yaxşı alt-seqmentə bölə bilərik: [1, 3, 3] və [4, 7, 5, 4].
[1, 3, 3] yaxşıdır: 1 + 3 > 3.
[4, 7, 5, 4] yaxşıdır: , , uzunluğunda çubuqlar bir üçbucaq yaradır (4 + 4 > 5).
Sorğu "2 3 8": Alt-massiv [3, 4, 7, 5, 4, 3]-dir. Biz onu yaxşı alt-seqmentə bölə bilərik: [3, 4, 7, 5, 4, 3].
[3, 4, 7, 5, 4, 3] yaxşıdır: , , uzunluğunda çubuqlar bir üçbucaq yaradır (3 + 4 > 5).
( xal) n,q \le 1000, yeniləmə sorğuları yoxdur;
( xal) n,q \le 1000;
( xal) yeniləmə sorğuları yoxdur;
( xal) a_i \le 100, sorğulardakı hər -dən kiçik və ya bərabərdir;
( xal) n \le 10^5;
( xal) əlavə məhdudiyyətlər yoxdur.