[Solution] Mark and Professor Koro Codeforces Solution

E. Mark and Professor Koro

time limit per test

2 seconds

memory limit per test

256 megabytes

input

standard input

output

standard output

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$n$ positive integers a1,a2,…,an$a_1,a_2,\dots ,a_n$ on it.

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

• select an integer x$x$ that appears at least 2$2$ times on the board,
• erase those 2$2$ appearances, and
• write x+1$x+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$q$ times. Each time, he will choose positive integers k$k$ and l$l$, then change ak$a_k$ to l$l$. After each update, he will ask Mark the same question again.

Solution Click Below:-  👉CLICK HERE👈

👇👇👇👇👇

Help Mark answer these questions faster than Professor Koro!

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

Mark and the Online Exam Codeforces Solution

Mark and Professor Koro Codeforces Solution

Mark and Lightbulbs Codeforces Solution

Mark and His Unfinished Essay Codeforces Solution

Mark the Dust Sweeper Codeforces Solution

Mark the Photographer Codeforces Solution

 updates.

Input

The first line of the input contains two integers n$n$ and q$q$ (2≤n≤2⋅105$2\le n\le 2\cdot {10}^5$, 1≤q≤2⋅105$1\le q\le 2\cdot {10}^5$) — the length of the sequence a$a$ and the number of updates, respectively.

The second line contains n$n$ integers a1,a2,…,an$a_1,a_2,\dots ,a_n$ (1≤ai≤2⋅105$1\le a_i\le 2\cdot {10}^5$)

Then, q$q$ lines follow, each consisting of two integers k$k$ and l$l$ (1≤k≤n$1\le k\le n$, 1≤l≤2⋅105$1\le l\le 2\cdot {10}^5$), telling to update ak$a_k$ to l$l$.

Output

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