Mark and Professor Koro solution codeforces

Mark and Professor Koro solution codeforces

Solution – CLICK HERE

After watching a certain anime before going to sleep, Mark dreams of standing in an old classroom with a blackboard that has a sequence of n positive integers 1,2,,a1,a2,…,an on it.

Then, professor Koro comes in. He can perform the following operation:

  • select an integer x that appears at least 22 times on the board,
  • erase those 22 appearances, and
  • write +1x+1 on the board.

Professor Koro then asks Mark the question, “what is the maximum possible number that could appear on the board after some operations?”

Mark quickly solves this question, but he is still slower than professor Koro. Thus, professor Koro decides to give Mark additional challenges. He will update the initial sequence of integers q times. Each time, he will choose positive integers k and l, then change ak to l. After each update, he will ask Mark the same question again.

Help Mark answer these questions faster than Professor Koro!

Note that the updates are persistent. Changes made to the sequence a will apply when processing future updates.

Input

The first line of the input contains two integers n and q (221052≤n≤2⋅105121051≤q≤2⋅105) — the length of the sequence a and the number of updates, respectively.

The second line contains n integers 1,2,,a1,a2,…,an (121051≤ai≤2⋅105)

Then, q lines follow, each consisting of two integers k and l (11≤k≤n121051≤l≤2⋅105), telling to update ak to l.

Output

Print q lines. The i-th line should consist of a single integer — the answer after the i-th update.

Examples
input

Copy
5 4
2 2 2 4 5
2 3
5 3
4 1
1 4
output

Copy
6
5
4
5
input

Copy
2 1
200000 1
2 200000
output

Copy
200001
Note

In the first example test, the program must proceed through 44 updates.

The sequence after the first update is [2,3,2,4,5][2,3,2,4,5]. One sequence of operations that achieves the number 66 the following.

  • Initially, the blackboard has numbers [2,3,2,4,5][2,3,2,4,5].
  • Erase two copies of 22 and write 33, yielding [3,4,5,3][3,4,5,3].
  • Erase two copies of 33 and write 44, yielding [4,5,4][4,5,4].
  • Erase two copies of 44 and write 55, yielding [5,5][5,5].
  • Erase two copies of 55 and write 66, yielding [6][6].

Then, in the second update, the array is changed to [2,3,2,4,3][2,3,2,4,3]. This time, Mark cannot achieve 66. However, one sequence that Mark can use to achieve 55 is shown below.

  • Initially, the blackboard has [2,3,2,4,3][2,3,2,4,3].
  • Erase two copies of 22 and write 33, yielding [3,4,3,3][3,4,3,3].
  • Erase two copies of 33 and write 44, yielding [3,4,4][3,4,4].
  • Erase two copies of 44 and write 55, yielding [3,5][3,5].

In the third update, the array is changed to [2,3,2,1,3][2,3,2,1,3]. One way to achieve 44 is shown below.

  • Initially, the blackboard has [2,3,2,1,3][2,3,2,1,3].
  • Erase two copies of 33 and write 44, yielding [2,2,1,4][2,2,1,4].

Solution – CLICK HERE

Leave a Comment

Your email address will not be published.