Robbery
In the country of Olympia, the banking system is highly advanced, and residents are keen to deposit their savings in banks. There are N banks arranged in a row, where bank i contains a[i] tugriks. Initially, there is no security system to prevent robberies. However, if bank b is robbed on the evening of day d, by the next morning, a security system will be installed in the neighboring banks (b − 1 and b + 1), making them impossible to rob. On the morning of day d + i (i > 0), the security system will extend to banks b − i and b + i. This process continues until all banks are secure. A bank that has been robbed cannot be robbed again.
In Olympia, even criminals are adept at solving Olympiad problems, so the government is confident that any planned series of robberies will be executed optimally, maximizing the total amount of tugriks stolen before the security system is fully installed. Additionally, criminals rob no more than one bank per day and only operate in the evening.
The banking system, assessing potential losses from robberies, considers M+1 successive scenarios of fund allocation in banks. Each scenario differs from the previous one by the amount of money in one of the banks.
Task
Write a program to calculate the maximum possible losses from robberies for each scenario of fund allocation in banks.
Input
The first line of input contains the integers N and M — the number of banks and the number of operations changing the amount of tugriks. The next line contains N integers a[i], representing the initial amount of tugriks in the banks. The following M lines each contain a pair of integers B and T, indicating that after the respective operation, bank number B will have T tugriks.
Output
For each i (0 ≤ i ≤ M), output the maximum number of tugriks that criminals can steal after performing i operations, each on a new line.
Evaluation
The test set consists of 3 blocks, with the following additional conditions:
10% of points:
1 ≤ N, M ≤ 8.20% of points:
1 ≤ N, M ≤ 1000.70% of points:
1 ≤ N, M ≤ 100,000.
Explanation. In the scheme below, 0 denotes a robbed bank, and -1 denotes a bank where a security system has already been installed.
For the initial allocation scenario, the robbers' actions will be as follows:
6 7 5 6 2 2 4 — initial state;
6 7 5 0 2 2 4 — robbed the fourth bank (6 tugriks);
6 7 -1 0 -1 2 4 — the next morning, a security system is installed in the neighboring banks;
6 0 -1 0 -1 2 4 — robbed the second bank (7 tugriks);
-1 0 -1 0 -1 -1 4 — a security system is installed in the first bank (due to the robbery of the second) and in the sixth (due to the robbery of the fourth 2 days ago);
-1 0 -1 0 -1 -1 0 — rob the last bank (4 tugriks).
In total, the robbers have 17 tugriks.
For the last allocation scenario: 6 7 5 6 2 5 6, the robbers can obtain 6 + 7 + 6 = 19 tugriks by robbing the fourth, second, and then the seventh banks.