# Can you answer these queries - 3

Very easy

Execution time limit is 1 second

Runtime memory usage limit is 64 megabytes

You are given an integer sequence a_1, a_2, ..., a_n (|a_i| ≤ 10000 , 1 ≤ n ≤ 50000). On this sequence you have to apply m (m ≤ 50000) operations:

modify the i-th element of the sequence

for given x and y print MAX {a_i + a_{i+1} + ... + a_j, x ≤ i ≤ j ≤ y}

## Input

The first line contains the integer n. The following line contains n integers, representing the sequence a_1, a_2, ..., a_n. The third line contains the integer m. The next m lines contain the operations in following form:

0 x y: modify a_x into y (|y| ≤ 10000).

1 x y: print MAX {a_i + a_{i+1} + ... + a_j, x ≤ i ≤ j ≤ y}

## Output

For each query, print an integer as the problem required.

## Examples

Input #1

Answer #1

Submissions 849

Acceptance rate 55%