Vinni-Pux 2
Əgər əvvəlki tapşırığı oxumusunuzsa, Vinni-Pux haqqında hekayəni bilirsiniz. Bu tapşırıqda da eyni vəziyyət baş verir, lakin indi Vinni bəzən bir dəfəyə bir neçə çəlləyi başqaları ilə dəyişdirir. Amma o, hələ də yalnız yan-yana duran çəlləkləri dəyişə bilər ki, qeydiyyat aparmaq rahat olsun. Bundan əlavə, biz bilirik ki, əgər o, çəlləkləri dəyişirsə, bütün yeniləri bir partiyadan olacaq, buna görə də onların şirinliyi eyni olacaq. Sizin tapşırığınız yenidən ayının səhər yeməyi üçün istifadə edə biləcəyi maksimum çəllək sayını tapmaqdır.
Giriş verilənləri
Birinci sətirdə bir ədəd N (1 ≤ N ≤ 10^6) - Vinni-Puxun zirzəmisindəki çəlləklərin sayı var. Növbəti sətirdə N ədəd var - çəlləklərin şirinliyi (bütün ədədlər 10^9-dan çox deyil). Sonra M (1 ≤ M ≤ 10^5) - sorğuların sayı gəlir. Sonra M sətir gəlir, sətirdəki ilk ədəd sorğunun növüdür. Əgər bu ədəd 1-ə bərabərdirsə, onda iki ədəd, l və r (1 ≤ l ≤ r ≤ N) olacaq və siz tapşırığın cavabını tapmalısınız. Əgər sorğunun nömrəsi 2-dirsə, onda üç ədəd l, r, v gəlir və bu o deməkdir ki, l-dən r-ə qədər olan çəlləklərin şirinliyi dəyişib və indi v-yə bərabərdir.
Çıxış verilənləri
Bir nömrəli hər bir sorğu üçün [l; r] aralığında ardıcıl gedən və birincisindən başqa hamısının şirinliyi əvvəlkindən az olmayan maksimum çəllək sayını çıxarın.