maxq

Johnie a început să se joace cu un vector de numere. El dispune iniţial de un vector $V$ cu $N$ numere întregi (numerotate de la $0$ la $N - 1$) şi poate efectua următoarele operaţii:

• schimbarea elementului de pe poziţia $p$ cu un alt număr întreg;
• aflarea subsecvenţei de sumă maximă din $V$ inclusă între indicii $a$ şi $b$;

Cerinţă

Ajutaţi-l pe Johnie să efectueze repede operaţiile de mai sus.

Date de intrare

Fisierul maxq.in conţine pe prima linie numărul $N$ reprezentând dimensiunea vectorului. Pe următoarea linie se găsesc $N$ elemente reprezentând valorile iniţiale ale vectorului. Urmatoarea linie conţine $M$, reprezentând numărul de operaţii. Pe fiecare dintre următoarele $M$ linii sunt descrise cele $M$ operaţii în forma următoare:

• 0 i p: numărul 0 de la început codifică faptul că operaţia curentă este una de schimbare; astfel elementul de pe poziţia $i$ a vectorului se înlocuieşte cu numarul întreg $p$;
• 1 a b: numărul 1 de la început codifică faptul că operaţia curentă este o întrebare; astfel se cere să se afle subsecvenţa de sumă maximă din vector inclusă între indicii $a$ şi $b \ (a \leq b)$;

Date de ieşire

Fişierul maxq.out trebuie să conţină un număr de linii egal cu numărul de întrebări din fişierul de intrare. Pe linia $i$ se cere să se afişeze un singur număr reprezentând suma maximă ce se poate obţine în contextul întrebării $i$ din fişierul de intrare $(i=1,2,\dots)$; în cazul în care vor exista doar subsecvenţe de sumă negativă se va afişa 0.

Restricţii si precizări

• $1 \leq N \leq 200 \ 000$
• $1 \leq M \leq 200 \ 000$
• toate elementele vectorului aparţin intervalului $[-100 \ 000, 100 \ 000]$
• definim o subsecvenţă ca fiind un şir de termeni consecutivi din vector, iar suma ei se obţine adunând elementele ce o compun
• există cel puţin o întrebare.
• pentru $20\%$ din teste se garantează $N \leq 5 \ 000$

Exemplu

maxq.in

5
1 -10 4 -1 9
4
1 0 3
0 1 1
1 0 3
1 2 4	

maxq.out

4
6
12

Explicații

Pentru prima întrebare se alege subsecvenţa formată de elementul pe poziţia $2$ din vector. Pentru a doua întrebare se aleg primele $3$ elemente din vector (elementul de pe poziţia $1$ a fost schimbat). Pentru a treia întrebare se aleg toate elementele din intervalul cerut.