Vinni-Pux
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ə N bal çəlləyi var, bunlar ardıcıl olaraq 1-dən 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.
Giriş verilənləri
Birinci sətirdə N (1 ≤ N ≤ 10^6) - Vinni-Puxun zirzəmisindəki çəlləklərin sayı verilir. Növbəti sətirdə N ədəd - çəlləklərin şirinliyi verilir (bütün ədədlər 10^9-dan çox deyil). Sonra M (1 ≤ M ≤ 10^5) - sorğuların sayı verilir. Növbəti M sətirdə üç ədəd: sorğunun tipi, l və r (1 ≤ l ≤ r ≤ 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, l nömrəli çəlləkdəki şirinliyin dəyişdiyini və indi r-ə bərabər olduğunu bildirir.
Çıxış verilənləri
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.