Vinni-Pux#4487
Hər kəsə məlumdur ki, Vinni-Puxun ən çox sevdiyi şey — əlbəttə ki, baldır. Bu gün səhər də ayı bal yemək istədi. Onun zirzəmisində rəfdə bal çəlləyi var, bunlar ardıcıl olaraq -dən -ə qədər nömrələnib. Naməlum səbəblərdən bütün çəlləklərdə fərqli "şirinlikdə" bal var, buna görə də Vinni məyus olmamaq üçün elə səhər yeməyi yeyə bilər ki, hər növbəti çəllək əvvəlkindən az şirin olmasın. Bundan əlavə, o, həmişə balı ardıcıl olaraq yeyir ki, səhv etməsin. Sizin vəzifəniz, ayının öz qaydalarına əməl edərək yeyə biləcəyi maksimum çəllək sayını hesablamaqdır.
Birinci sətirdə (1 \leq N \leq 10^6) — Vinni-Puxun zirzəmisindəki çəlləklərin sayı verilir. Növbəti sətirdə ədəd — çəlləklərin şirinliyi verilir (bütün ədədlər 10^9-dan çox deyil). Sonra (1 \leq M \leq 10^5) — sorğuların sayı verilir. Növbəti sətirdə üç ədəd: sorğunun tipi, və (1 \leq l \leq r \leq N) verilir. Hər bir birinci nömrəli sorğu üçün məsələnin cavabını tapın. İkinci nömrəli sorğu, nömrəli çəlləkdəki şirinliyin dəyişdiyini və indi -ə bərabər olduğunu bildirir.
Hər bir birinci nömrəli sorğu üçün [l; r] aralığında ardıcıl gedən və birincidən başqa hamısının şirinliyi əvvəlkindən az olmayan maksimum çəllək sayını çıxarın.
Nümunə 1