Can you answer these queries - 3

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