Yaxşı üçbucaqlar#524

Yaxşı üçbucaqlar

4 saniyə
256 meqabayt
Very hard

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:

Input

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).

Output

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.

Examples

Example 1

Loading
Loading

Note

İ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).

Scoring

  1. ( xal) n,q \le 1000, yeniləmə sorğuları yoxdur;

  2. ( xal) n,q \le 1000;

  3. ( xal) yeniləmə sorğuları yoxdur;

  4. ( xal) a_i \le 100, sorğulardakı hər -dən kiçik və ya bərabərdir;

  5. ( xal) n \le 10^5;

  6. ( xal) əlavə məhdudiyyətlər yoxdur.