eolymp
Problems

Can you answer these queries - 3

Can you answer these queries - 3

You are given an integer sequence a1, a2, ..., an (|ai| ≤ 10000 , 1 ≤ n50000). On this sequence you have to apply m (m50000) operations:

  • modify the i-th element of the sequence
  • for given x and y print MAX {ai + ai+1 + ... + aj, xijy}

Input

The first line contains the integer n. The following line contains n integers, representing the sequence a1, a2, ..., an. The third line contains the integer m. The next m lines contain the operations in following form:

  • 0 x y: modify ax into y (|y| ≤ 10000).
  • 1 x y: print MAX {ai + ai+1 + ... + aj, xijy}

Output

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

Time limit 1 second
Memory limit 64 MiB
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