## OCC '19 G2 - A Guessing Game

View as PDF

Points: 25
Time limit: 0.6s
Memory limit: 512M

Problem type

Alex is playing a game with William. Alex gets two sequences: sequence and sequence , each of which has numbers. Alex will show William the sequence but not the sequence . The objective of this game is to figure out each number in sequence .

During the game, William can ask Alex questions as many times as he wants. For each question, William will pick up an interval () and ask Alex the sum of for . Alex will answer William's question, but will charge William for dollars. William wants to use the minimal cost to figure out the sequence .

Since William is bored, he decides to play this game for rounds. Before each round, Alex will re-generate the sequence . However, Alex is too lazy to re-generate the cost sequence . So, Alex will only change one number from the previous sequence . Given the number which Alex will change and the new value, can you help William to find out the minimum cost for figuring out the sequence in each round of the game?

#### Input Specification

The first line contains two integers, and , the number of elements in each sequence and the number of rounds William will play.

The second line contains integers, the initial sequence .

lines of input follow. The line contains two integers, and , which means Alex will pick up the element from the previous sequence and replace it with the new value before the round .

#### Output Specification

Print lines. The line contains one integer, the minimum cost for William to figure out the sequence in game .

#### Sample Input

5 3
1 2 3 4 5
1 2
3 4
5 6

#### Sample Output

5
6
10

#### Explanation for Sample Output

The initial sequence is .

Before round , Alex will change to be , i.e. the new sequence is .

In round , William can ask questions for , , , and with the total cost of .

Before round , Alex will change to be , i.e. the new sequence is .

In round , William can ask questions for , , , and with the total cost of .

#### Constraints

For all test cases, , , and .