Problems
Can you answer these queries - 3
Can you answer these queries - 3
You are given an integer sequence \textbf{a_1}, \textbf{a_2}, ..., \textbf{a_n} (|\textbf{a_i}| ≤ \textbf{10000} , 1 ≤ \textbf{n} ≤ \textbf{50000}). On this sequence you have to apply \textbf{m} (\textbf{m} ≤ \textbf{50000}) operations:
\begin{itemize}
\item modify the \textbf{i}-th element of the sequence
\item for given \textbf{x} and \textbf{y} print \textbf{MAX} \{\textbf{a_i} + \textbf{a_\{i+1\}} + ... + \textbf{a_j}, \textbf{x} ≤ \textbf{i} ≤ \textbf{j} ≤ \textbf{y}\}
\end{itemize}
\InputFile
The first line contains the integer \textbf{n}. The following line contains \textbf{n} integers, representing the sequence \textbf{a_1}, \textbf{a_2}, ..., \textbf{a_n}. The third line contains the integer \textbf{m}. The next \textbf{m} lines contain the operations in following form:
\begin{itemize}
\item \textbf{0 x y}: modify \textbf{a_x} into \textbf{y} (|\textbf{y}| ≤ \textbf{10000}).
\item \textbf{1 x y}: print \textbf{MAX} \{\textbf{a_i} + \textbf{a_\{i+1\}} + ... + \textbf{a_j}, \textbf{x} ≤ \textbf{i} ≤ \textbf{j} ≤ \textbf{y}\}
\end{itemize}
\OutputFile
For each query, print an integer as the problem required.
Input example #1
4 1 2 3 4 4 1 1 3 0 3 -3 1 2 4 1 3 3
Output example #1
6 4 -3