GSS3 - Can you answer these queries III


You are given a sequence A of N (N <= 50000) integers between -10000 and 10000. On this sequence you have to apply M (M <= 50000) operations:
modify the i-th element in the sequence or for given x y print max{Ai + Ai+1 + .. + Aj | x<=i<=j<=y }.

Input

The first line of input contains an integer N. The following line contains N integers, representing the sequence A1..AN.
The third line contains an 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 | x<=i<=j<=y }.

Output

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

Example

Input:
4
1 2 3 4
4
1 1 3
0 3 -3
1 2 4
1 3 3

Output:
6
4
-3

hide comments
Anirudh Rayabharam: 2014-07-20 15:24:20

This is complete nonsense. Why is the source limit so low? The standard is 50000 Bytes.

Mike OBeirne: 2014-05-22 05:40:50

For Java, I had to use a faster scanner (using BufferedInputReader), as well as using StringBuilder for the output. Was able to finally get it to pass, though!

The Bear: 2014-04-28 16:58:47

Can anyone please explain why the test case for 1 2 4 is equal to 4 and not 3? Is this an incorrect test case?

Zhao Xinyi: 2014-03-14 08:37:18

what does "wrong answer #0" mean?

hiddenman: 2014-02-09 20:09:21

enjy a lot in doing this question .....
evn grt learning experience.... :)

harsh: 2014-01-15 14:24:50

0.21 sec..\m/..

The Wizard: 2013-09-17 01:32:20

I think in this problem using segment tree is so useful

nishchay: 2013-09-01 06:09:57

AC :D
Note: For Java Users, Using Split(" ") with BufferedReader resulting in NZEC, do take care not count any space or enter char that can come(I guess there are many and not single " ").

!!.Nginx.!!: 2013-05-16 13:42:07

how query: 1 2 4 giving output=4 shouldn't it be 3 (2+(-3)+4)

Alexander Maryanovsky: 2013-05-11 12:39:00

Please increase the source limit. Some languages are more verbose than others and it's ridiculous that I have to give all my variables a 1-character name just to fit a neat-looking implementation into 5k.


Added by:Bin Jin
Date:2007-08-03
Time limit:0.330s
Source limit:5000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: CPP
Resource:own problem