Задачі
Чи можете Ви відповісти на ці питання - 3
Чи можете Ви відповісти на ці питання - 3
Задана послідовність цілих чисел \textbf{a_1}, \textbf{a_2}, ..., \textbf{a_n} (|\textbf{a_i}| ≤ \textbf{10000} , 1 ≤ \textbf{n} ≤ \textbf{50000}). Над ній Вам слід виконати \textbf{m} (\textbf{m} ≤ \textbf{50000}) операцій:
\begin{itemize}
\item модифікувати \textbf{i}-ий елемент послідовності
\item для заданих \textbf{x та y} вивести \textbf{MAX} \{\textbf{a_i} + \textbf{a_\{i+1\}} + ... + \textbf{a_j}, \textbf{x} ≤ \textbf{i} ≤ \textbf{j} ≤ \textbf{y}\}
\end{itemize}
\InputFile
Перший рядок містить значення \textbf{n}. Наступний рядок містить \textbf{n} цілих чисел, що задають послідовнвсть \textbf{a_1}, \textbf{a_2}, ..., \textbf{a_n}. Третій рядок містить число \textbf{m}. Наступні \textbf{m} рядків містять запити вигляду:
\begin{itemize}
\item \textbf{0 x y}: змінити \textbf{a_x} на \textbf{y} (|\textbf{y}| ≤ \textbf{10000}).
\item \textbf{1 x y}: вивести \textbf{MAX} \{\textbf{a_i} + \textbf{a_\{i+1\}} + ... + \textbf{a_j}, \textbf{x} ≤ \textbf{i} ≤ \textbf{j} ≤ \textbf{y}\}
\end{itemize}
\OutputFile
Для кожного запиту вивести відповідь як вимагається в задачі.
Вхідні дані #1
4 1 2 3 4 4 1 1 3 0 3 -3 1 2 4 1 3 3
Вихідні дані #1
6 4 -3