Bu suallara cavab verə bilərsinizmi - 3

Verilmiş tam ədədlər ardıcıllığı a_1, a_2, ..., a_n (|a_i| ≤ 10000, 1 ≤ n ≤ 50000) üzərində m (m ≤ 50000) əməliyyat yerinə yetirməlisiniz:

• Ardıcıllığın i-ci elementini dəyişmək

• Verilmiş x və y üçün MAX {a_i + a_{i+1} + ... + a_j, x ≤ i ≤ j ≤ y} tapmaq

Giriş verilənləri

Birinci sətir n dəyərini ehtiva edir. Növbəti sətir ardıcıllığı təyin edən n tam ədəd ehtiva edir: a_1, a_2, ..., a_n. Üçüncü sətir m ədədini ehtiva edir. Sonrakı m sətir sorğuları ehtiva edir:

• 0 x y: a_x ədədini y ilə dəyişmək (|y| ≤ 10000).

• 1 x y: MAX {a_i + a_{i+1} + ... + a_j, x ≤ i ≤ j ≤ y} tapmaq

Çıxış verilənləri

Hər bir sorğu üçün tələb olunan cavabı çıxarın.

Nümunələr