Maximum Prefix Sum
You have an array of elements. An array of elements has prefix.
Prefix-1 has only the first element of the array.
Prefix-2 has the first two elements of the array.
Prefix-3 has the first three elements of the array
………..
Prefix-n-1 has the first n-1 elements of the array.
Prefix-n has the first n elements of the array.
There are also queries. In each query given two values and . You have to set into position in the array and print the maximum prefix sum among prefixes.
Input Format
First line of input contains and — length of the array and number of query.
Second line contains integers — initial value of the array.
Next line contains two integer and . You have to set into position in the array.
Constraints
Output Format
Print line one integer maximum prefix sum after each query.
Sample Input 0
3 3
10 -11 8
2 -12
2 -25
3 30
Sample Output 0
10
10
15
Explanation 0
After first query array look like [10,-12,8] and maximum prefix sum 10.
After second query array look like [10,-25,8] and maximum prefix sum 10.
After third query array look like [10,-25,30] and maximum prefix sum 15=10-25+30.
xxxxxxxxxxint main() { /* Enter your code here. Read input from STDIN. Print output to STDOUT */ return 0;}