Задана последовательность целых чисел \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 }и\textbf{ 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 Для каждого запроса вывести ответ как требуется в задаче.