values and a list of edits edits, where edits[i] = [pos, x].
The edits are applied one by one: an edit sets values[pos] = x. After each edit, find the largest sum you can collect by picking array elements so that no two picked elements are next to each other. Picking nothing is allowed and gives 0.
Return the sum of these answers over all edits, modulo 10⁹ + 7.
Recomputing everything after each edit is too slow; aim to update the answer faster than O(n).values=[4, 2, 6, 3], edits=[[2, -1], [3, 8]] → 19
After the first edit the array is [4, 2, -1, 3] and the best pick is 4 and 3: 7. After the second it is [4, 2, -1, 8], best 4 + 8 = 12. The answer is 7 + 12 = 19.
values=[-2, -7], edits=[[1, -3]] → 0
All numbers are negative, so picking nothing is best: the sum is 0.
values=[5, 5, 5], edits=[[1, 20], [1, 1]] → 30
pos < len(values)x ≤ 10⁵values=[4, 2, 6, 3], edits=[[2, -1], [3, 8]]
19
Run checks the first 3 tests in your browser. Submit checks all 88 tests on the server, hidden ones included.