Contiguous Park Selection

There is a road called "Park Road" near Xiaoxin's home, along which n parks are arranged from south to north. Initially, Xiaobai rated each park based on its scenery. Whenever Xiaoxin takes the dog for a walk, he specifies a range of parks from a to b (inclusive) from which Xiaobai can choose a contiguous segment of parks to play in. Naturally, Xiaobai wants the total score of the selected parks to be as high as possible.

Note that the scenery of some parks may change over time, so the scores might be updated.

Your task is to help Xiaobai by handling two types of operations on the list of parks:

• Update Operation: Change the score of a specified park.
• Query Operation: Given a range from a to b, find the maximum possible sum of a contiguous subsequence of parks within that range. Mathematically, for an array arr with indices running from a to b, you need to find the maximum value of \(\sum_{i=l}^{r} arr[i]\) where \(a \le l \le r \le b\).</p>

Input Format: See below.

inputFormat

The first line contains a single integer n \((1 \le n \le 10^5)\), the number of parks.

The second line contains n space-separated integers \(s_1, s_2, \ldots, s_n\) representing the initial scores of the parks \((-10^4 \le s_i \le 10^4)\).

The third line contains a single integer m \((1 \le m \le 10^5)\), the number of operations.

Each of the following m lines represents an operation. An operation is given in one of the following two formats:

• 0 pos val: Update the score of the park at position pos (1-indexed) to val.
• 1 a b: Query the maximum contiguous subarray sum within the range of parks from index a to b (inclusive).

outputFormat

For each query operation, print one line containing the maximum contiguous subarray sum for the specified range.

sample

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

9
9
10