Peng the Penguin has hired a chef to cook 
~N~ dishes for him daily. Peng assigns a value 
~A_i~ to each dish, which represents how much satisfaction he gains from that dish. If he really hates the dish, he will assign it a negative number. He wants to gain the most satisfaction possible, but he can only eat a consecutive portion of the meal because he's Peng. He needs someone to write a program to help him determine the maximum amount of satisfaction he can gain daily for 
~M~ days. Furthermore, the chef will only change one dish per day so he doesn't run out of ideas for dishes. The new dish can have the same satisfaction level as the previous one. Note that if the satisfaction Peng can gain by taking any consecutive portion of the meal is negative, he can choose to not take any portion and gain 
~0~ satisfaction as a result.
Input Specification
An integer ~N~, followed by ~N~ integers on the next line, with the 
~i^\text{th}~ integer representing ~A_i~.
This is followed by an integer ~M~, followed by ~M~ lines containing two integers each, 
~x~ and 
~y~, where the 
~x^\text{th}~ dish (0-indexed) now has ~y~ satisfaction value.
Output Specification
~M+1~ integers on separate lines, with the ~i^\text{th}~ integer representing the maximum satisfaction Peng can obtain on day 
~i~.
Constraints
For all subtasks:
~|A_i| \le 10^4~
Subtask 1 [15%]
~1 \le N, M \le 100~
Subtask 2 [50%]
~1 \le N, M \le 10^4~
Subtask 3 [35%]
~1 \le N, M \le 10^6~
Sample Input
5
3 -4 2 5 1
3
1 1
2 -6
1 -3
Sample Output
8
12
6
6
Explanation for Sample Output
On the 1st day, the dishes were 3 -4 2 5 1, and Peng will pick 2 5 1.
On the 2nd day, the dishes were 3 1 2 5 1, and Peng eats everything.
On the 3rd day, the dishes were 3 1 -6 5 1, and Peng will pick 5 1.
On the 4th day, the dishes were 3 -3 -6 5 1, and Peng will pick 5 1.
Comments
This comment is hidden due to too much negative feedback. Show it anyway.