Vinni-Pux 2#4488
Əgər əvvəlki problemi oxumusunuzsa, Vinni-Puxdan bəhs edən hekayəni bilirsiniz. Bu tapşırıqda da oxşar bir vəziyyətdir, lakin indi Vinni bəzən bütöv bir qrup çəlləyi birdən dəyişir. Lakin, o yalnız qonşu olan çəlləkləri dəyişə bilər ki, hesab-kitabı asan aparsın. Bundan başqa, hər dəfə Vinni çəlləkləri dəyişəndə, onların hamısı eyni partiyadandır, yəni şirinlik səviyyələri tamamilə eynidir. Tapşırığınız, yenə də, aşağıda təsvir olunan hər sorğu üçün ayının səhər yeməyi üçün əldə edə biləcəyi çəlləklərin maksimal sayını müəyyənləşdirməkdir.
Birinci sətirdə bir tam ədəd (1 \le N \le 10^6) — Vinni-Puxun zirzəmisindəki çəlləklərin sayı verilir.
İkinci sətirdə ədəd verilir — çəlləklərin şirinlik səviyyələri (hər biri 10^9-u keçmir).
Daha sonra bir sətirdə bir tam ədəd (1 \le M \le 10^5) — sorğuların sayı verilir.
Sonrakı sətirin hər biri sorğunu təsvir edir.
- Sətrdəki birinci ədəd sorğunun tipini bildirir. - Əgər -dirsə, sonra iki tam ədəd və verilir (1 \le l \le r \le N). Bu sorğu üçün aşağıda təsvir olunan şəkildə cavab verməlisiniz. - Əgər -dirsə, sonra üç tam ədəd , və verilir. Bu, -dən -yə qədər bütün çəlləklərin şirinlik səviyyəsinin -yə dəyişdirilməsi deməkdir.
Hər tipli sorğu üçün, [l; r] seqmentində ardıcıl olaraq elə maksimal çəllək sayını çap edin ki, oradakı hər bir çəlləyin şirinliyi əvvəlkindən az olmasın (birincidən başqa).
Nümunə 1