- Time limit: 1.00 s
- Memory limit: 512 MB
There is an array consisting of integers. Some values of the array will be updated, and after each update, your task is to report the maximum subarray sum in the array.
Input
The first input line contains integers and : the size of the array and the number of updates. The array is indexed .
The next line has integers: : the initial contents of the array.
Then there are lines describing the changes. Each line has two integers and : the value at position becomes .
Output
After each update, print the maximum subarray sum. Empty subarrays (with sum ) are allowed.
Constraints
Example
Input:
5 3 1 2 -3 5 -1 2 6 3 1 2 -2
Output:
9 13 6