Mark and Professor Koro (Codeforces 1705E)
Tags: Greedy, bitmasks

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 $$$a_1, a_2,\dots,a_n$$$ on it.Then, professor Koro comes in. He can perform the following operation:  select an integer $$$x$$$ that appears at least $$$2$$$ times on the board,  erase those $$$2$$$ appearances, and  write $$$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$$$ times. Each time, he will choose positive integers $$$k$$$ and $$$l$$$, then change $$$a_k$$$ 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$$$ ($$$2\leq n\leq 2\cdot 10^5$$$, $$$1\leq q\leq 2\cdot 10^5$$$) — the length of the sequence $$$a$$$ and the number of updates, respectively.The second line contains $$$n$$$ integers $$$a_1,a_2,\dots,a_n$$$ ($$$1\leq a_i\leq 2\cdot 10^5$$$)Then, $$$q$$$ lines follow, each consisting of two integers $$$k$$$ and $$$l$$$ ($$$1\leq k\leq n$$$, $$$1\leq l\leq 2\cdot 10^5$$$), telling to update $$$a_k$$$ to $$$l$$$.

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

Note: In the first example test, the program must proceed through $$$4$$$ updates.The sequence after the first update is $$$[2,3,2,4,5]$$$. One sequence of operations that achieves the number $$$6$$$ the following.   Initially, the blackboard has numbers $$$[2,3,2,4,5]$$$.  Erase two copies of $$$2$$$ and write $$$3$$$, yielding $$$[3,4,5,\color{red}{3}]$$$.  Erase two copies of $$$3$$$ and write $$$4$$$, yielding $$$[4,5,\color{red}{4}]$$$.  Erase two copies of $$$4$$$ and write $$$5$$$, yielding $$$[5,\color{red}{5}]$$$.  Erase two copies of $$$5$$$ and write $$$6$$$, yielding $$$[\color{red}{6}]$$$. Then, in the second update, the array is changed to $$$[2,3,2,4,3]$$$. This time, Mark cannot achieve $$$6$$$. However, one sequence that Mark can use to achieve $$$5$$$ is shown below.   Initially, the blackboard has $$$[2,3,2,4,3]$$$.  Erase two copies of $$$2$$$ and write $$$3$$$, yielding $$$[3,4,3,\color{red}{3}]$$$.  Erase two copies of $$$3$$$ and write $$$4$$$, yielding $$$[3,4,\color{red}{4}]$$$.  Erase two copies of $$$4$$$ and write $$$5$$$, yielding $$$[3,\color{red}{5}]$$$. In the third update, the array is changed to $$$[2,3,2,1,3]$$$. One way to achieve $$$4$$$ is shown below.   Initially, the blackboard has $$$[2,3,2,1,3]$$$.  Erase two copies of $$$3$$$ and write $$$4$$$, yielding $$$[2,2,1,\color{red}{4}]$$$. 

Sample Inputs:
5 4
2 2 2 4 5
2 3
5 3
4 1
1 4

2 1
200000 1
2 200000

Sample Outputs:
6
5
4
5

200001

Solution (Python):
import sys, os, io
input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline

def f(u, v):
    if v == 1:
        for w in range(u * m, (u + 1) * m):
            x[w] = 1
        cnt[u] = m
    else:
        for w in range(u * m, (u + 1) * m):
            x[w] = 0
        cnt[u] = 0
    y[u] = 0
    return
(n, q) = map(int, input().split())
a = [0] + list(map(int, input().split()))
l = 2 * pow(10, 5) + 35
m = 333
l = (l // m + 1) * m
inf = pow(10, 9) + 1
x = [0] * l
for i in a[1:]:
    x[i] += 1
for i in range(1, l - 1):
    x[i + 1] += x[i] // 2
    x[i] %= 2
la = inf
ans0 = 0
n = l // m
cnt = [0] * (n + 1)
for i in range(l - 1, -1, -1):
    if x[i]:
        ans0 = max(ans0, i)
        cnt[i // m] += 1
y = [0] * (n + 1)
ans = []
for _ in range(q):
    (k, l) = map(int, input().split())
    ak = a[k]
    if ak == l:
        ans.append(ans0)
        continue
    p = 1 if ak < l else 0
    i = ak // m
    if y[i]:
        f(i, y[i])
    if x[ak]:
        x[ak] -= 1
        cnt[i] -= 1
    else:
        z = n * m
        for j in range(ak, (i + 1) * m):
            if x[j]:
                z = j
                break
        if z == n * m:
            for j in range(i + 1, n):
                if y[j] == 2:
                    continue
                elif y[j] == 1:
                    f(j, y[j])
                    z = j * m
                    break
                elif not cnt[j]:
                    continue
                else:
                    for u in range(j * m, (j + 1) * m):
                        if x[u]:
                            z = u
                            break
                    break
        j = ak
        while j % m and j ^ z:
            x[j] = 1
            cnt[j // m] += 1
            j += 1
        while j + m < z:
            y[j // m] = 1
            j += m
        while j ^ z:
            x[j] = 1
            cnt[j // m] += 1
            j += 1
        x[z] = 0
        cnt[z // m] -= 1
    a[k] = l
    ak = a[k]
    i = ak // m
    if y[i]:
        f(i, y[i])
    if not x[ak]:
        x[ak] += 1
        cnt[i] += 1
    else:
        z = n * m
        for j in range(ak, (i + 1) * m):
            if not x[j]:
                z = j
                break
        if z == n * m:
            for j in range(i + 1, n):
                if y[j] == 1:
                    continue
                elif y[j] == 2:
                    f(j, y[j])
                    z = j * m
                    break
                elif not cnt[j] ^ m:
                    continue
                else:
                    for u in range(j * m, (j + 1) * m):
                        if not x[u]:
                            z = u
                            break
                    break
        j = ak
        while j % m and j ^ z:
            x[j] = 0
            cnt[j // m] -= 1
            j += 1
        while j + m < z:
            y[j // m] = 2
            j += m
        while j ^ z:
            x[j] = 0
            cnt[j // m] -= 1
            j += 1
        x[z] = 1
        cnt[z // m] += 1
    if p:
        if ans0 < l:
            ans0 = l
        elif x[ans0 + 1] or y[(ans0 + 1) // m] == 1:
            ans0 += 1
    else:
        while not x[ans0] or y[ans0 // m] == 2:
            if y[ans0 // m] == 2 or not cnt[ans0 // m]:
                ans0 = ans0 // m * m - 1
            else:
                ans0 -= 1
    ans.append(ans0)
sys.stdout.write('\n'.join(map(str, ans)))

Solution (Python):
class lazy_segtree:

    def update(self, k):
        self.d[k] = self.op(self.d[2 * k], self.d[2 * k + 1])

    def all_apply(self, k, f):
        self.d[k] = self.mapping(f, self.d[k])
        if k < self.size:
            self.lz[k] = self.composition(f, self.lz[k])

    def push(self, k):
        self.all_apply(2 * k, self.lz[k])
        self.all_apply(2 * k + 1, self.lz[k])
        self.lz[k] = self.identity

    def __init__(self, V, OP, E, MAPPING, COMPOSITION, ID):
        self.n = len(V)
        self.log = (self.n - 1).bit_length()
        self.size = 1 << self.log
        self.d = [E for i in range(2 * self.size)]
        self.lz = [ID for i in range(self.size)]
        self.e = E
        self.op = OP
        self.mapping = MAPPING
        self.composition = COMPOSITION
        self.identity = ID
        for i in range(self.n):
            self.d[self.size + i] = V[i]
        for i in range(self.size - 1, 0, -1):
            self.update(i)

    def set(self, p, x):
        assert 0 <= p and p < self.n
        p += self.size
        for i in range(self.log, 0, -1):
            self.push(p >> i)
        self.d[p] = x
        for i in range(1, self.log + 1):
            self.update(p >> i)

    def get(self, p):
        assert 0 <= p and p < self.n
        p += self.size
        for i in range(self.log, 0, -1):
            self.push(p >> i)
        return self.d[p]

    def prod(self, l, r):
        assert 0 <= l and l <= r and (r <= self.n)
        if l == r:
            return self.e
        l += self.size
        r += self.size
        for i in range(self.log, 0, -1):
            if l >> i << i != l:
                self.push(l >> i)
            if r >> i << i != r:
                self.push(r >> i)
        (sml, smr) = (self.e, self.e)
        while l < r:
            if l & 1:
                sml = self.op(sml, self.d[l])
                l += 1
            if r & 1:
                r -= 1
                smr = self.op(self.d[r], smr)
            l >>= 1
            r >>= 1
        return self.op(sml, smr)

    def all_prod(self):
        return self.d[1]

    def apply_point(self, p, f):
        assert 0 <= p and p < self.n
        p += self.size
        for i in range(self.log, 0, -1):
            self.push(p >> i)
        self.d[p] = self.mapping(f, self.d[p])
        for i in range(1, self.log + 1):
            self.update(p >> i)

    def apply(self, l, r, f):
        assert 0 <= l and l <= r and (r <= self.n)
        if l == r:
            return
        l += self.size
        r += self.size
        for i in range(self.log, 0, -1):
            if l >> i << i != l:
                self.push(l >> i)
            if r >> i << i != r:
                self.push(r - 1 >> i)
        (l2, r2) = (l, r)
        while l < r:
            if l & 1:
                self.all_apply(l, f)
                l += 1
            if r & 1:
                r -= 1
                self.all_apply(r, f)
            l >>= 1
            r >>= 1
        (l, r) = (l2, r2)
        for i in range(1, self.log + 1):
            if l >> i << i != l:
                self.update(l >> i)
            if r >> i << i != r:
                self.update(r - 1 >> i)

    def max_right(self, l, g):
        assert 0 <= l and l <= self.n
        assert g(self.e)
        if l == self.n:
            return self.n
        l += self.size
        for i in range(self.log, 0, -1):
            self.push(l >> i)
        sm = self.e
        while 1:
            while l % 2 == 0:
                l >>= 1
            if not g(self.op(sm, self.d[l])):
                while l < self.size:
                    self.push(l)
                    l = 2 * l
                    if g(self.op(sm, self.d[l])):
                        sm = self.op(sm, self.d[l])
                        l += 1
                return l - self.size
            sm = self.op(sm, self.d[l])
            l += 1
            if l & -l == l:
                break
        return self.n

    def min_left(self, r, g):
        assert 0 <= r and r <= self.n
        assert g(self.e)
        if r == 0:
            return 0
        r += self.size
        for i in range(self.log, 0, -1):
            self.push(r - 1 >> i)
        sm = self.e
        while 1:
            r -= 1
            while r > 1 and r % 2:
                r >>= 1
            if not g(self.op(self.d[r], sm)):
                while r < self.size:
                    self.push(r)
                    r = 2 * r + 1
                    if g(self.op(self.d[r], sm)):
                        sm = self.op(self.d[r], sm)
                        r -= 1
                return r + 1 - self.size
            sm = self.op(self.d[r], sm)
            if r & -r == r:
                break
        return 0
from sys import stdin
input = lambda : stdin.readline()[:-1]
m = 2 * 10 ** 5 + 100

def op1(x, y):
    return min(x, y)

def op2(x, y):
    return max(x, y)

def op(x, y):
    return (x & y & 1) + ((x | y) & 2)

def mapping(f, x):
    if f == id:
        return x
    else:
        return f

def comp(f, g):
    if f == id:
        return g
    return f
id = 1 << 20

def add(x):
    if seg.get(x) == 0:
        seg.apply(x, x + 1, 3)
        return

    def f(y):
        return y & 1 == 1
    r = seg.max_right(x, f)
    seg.apply(x, r, 0)
    seg.apply(r, r + 1, 3)
    return

def sub(x):
    if seg.get(x) == 3:
        seg.apply(x, x + 1, 0)
        return

    def f(y):
        return y & 2 == 0
    r = seg.max_right(x, f)
    seg.apply(x, r, 3)
    seg.apply(r, r + 1, 0)

def ans(x):

    def f(y):
        return y & 2 == 0
    l = seg.min_left(m, f)
    ANS[x] = l - 1
(n, q) = map(int, input().split())
a = list(map(int, input().split()))
c = [0] * m
for i in a:
    c[i] += 1
res = 0
for i in range(m):
    res //= 2
    res += c[i]
    c[i] = res % 2 * 3
seg = lazy_segtree(c, op, 1, mapping, comp, id)
ANS = [0] * q
for i in range(q):
    (x, y) = map(int, input().split())
    x -= 1
    sub(a[x])
    a[x] = y
    add(a[x])
    ans(i)
print(*ANS, sep='\n')

Solution (Python):
import sys
import os
from io import BytesIO, IOBase
from math import floor
from random import randint
import time
BUFSIZE = 8192

class FastIO(IOBase):
    newlines = 0

    def __init__(self, file):
        self._fd = file.fileno()
        self.buffer = BytesIO()
        self.writable = 'x' in file.mode or 'r' not in file.mode
        self.write = self.buffer.write if self.writable else None

    def read(self):
        while True:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            if not b:
                break
            ptr = self.buffer.tell()
            (self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
        self.newlines = 0
        return self.buffer.read()

    def readline(self):
        while self.newlines == 0:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            self.newlines = b.count(b'\n') + (not b)
            ptr = self.buffer.tell()
            (self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
        self.newlines -= 1
        return self.buffer.readline()

    def flush(self):
        if self.writable:
            os.write(self._fd, self.buffer.getvalue())
            (self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

    def __init__(self, file):
        self.buffer = FastIO(file)
        self.flush = self.buffer.flush
        self.writable = self.buffer.writable
        self.write = lambda s: self.buffer.write(s.encode('ascii'))
        self.read = lambda : self.buffer.read().decode('ascii')
        self.readline = lambda : self.buffer.readline().decode('ascii')
if sys.version_info[0] < 3:
    sys.stdin = BytesIO(os.read(0, os.fstat(0).st_size))
else:
    (sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
file = sys.stdin
if os.environ.get('USER') == 'loic':
    file = open('data.in')
line = lambda : file.readline().split()
ui = lambda : int(line()[0])
ti = lambda : map(int, line())
li = lambda : list(ti())

class IntervalList:

    def __init__(self, iterable=[], _load=5000):
        """"""
        values = sorted(iterable)
        self._len = _len = len(values)
        self._load = _load
        self._lists = _lists = [values[i:i + _load] for i in range(0, _len, _load)]
        self._list_lens = [len(_list) for _list in _lists]
        self._mins = [_list[0] for _list in _lists]
        self._fen_tree = []
        self._rebuild = True

    def _fen_build(self):
        """"""
        self._fen_tree[:] = self._list_lens
        _fen_tree = self._fen_tree
        for i in range(len(_fen_tree)):
            if i | i + 1 < len(_fen_tree):
                _fen_tree[i | i + 1] += _fen_tree[i]
        self._rebuild = False

    def _fen_update(self, index, value):
        """"""
        if not self._rebuild:
            _fen_tree = self._fen_tree
            while index < len(_fen_tree):
                _fen_tree[index] += value
                index |= index + 1

    def _fen_query(self, end):
        """"""
        if self._rebuild:
            self._fen_build()
        _fen_tree = self._fen_tree
        x = 0
        while end:
            x += _fen_tree[end - 1]
            end &= end - 1
        return x

    def _fen_findkth(self, k):
        """"""
        _list_lens = self._list_lens
        if k < _list_lens[0]:
            return (0, k)
        if k >= self._len - _list_lens[-1]:
            return (len(_list_lens) - 1, k + _list_lens[-1] - self._len)
        if self._rebuild:
            self._fen_build()
        _fen_tree = self._fen_tree
        idx = -1
        for d in reversed(range(len(_fen_tree).bit_length())):
            right_idx = idx + (1 << d)
            if right_idx < len(_fen_tree) and k >= _fen_tree[right_idx]:
                idx = right_idx
                k -= _fen_tree[idx]
        return (idx + 1, k)

    def _delete(self, pos, idx):
        """"""
        _lists = self._lists
        _mins = self._mins
        _list_lens = self._list_lens
        self._len -= 1
        self._fen_update(pos, -1)
        del _lists[pos][idx]
        _list_lens[pos] -= 1
        if _list_lens[pos]:
            _mins[pos] = _lists[pos][0]
        else:
            del _lists[pos]
            del _list_lens[pos]
            del _mins[pos]
            self._rebuild = True

    def _loc_left(self, value):
        """"""
        if not self._len:
            return (0, 0)
        _lists = self._lists
        _mins = self._mins
        (lo, pos) = (-1, len(_lists) - 1)
        while lo + 1 < pos:
            mi = lo + pos >> 1
            if value <= _mins[mi]:
                pos = mi
            else:
                lo = mi
        if pos and value <= _lists[pos - 1][-1]:
            pos -= 1
        _list = _lists[pos]
        (lo, idx) = (-1, len(_list))
        while lo + 1 < idx:
            mi = lo + idx >> 1
            if value <= _list[mi]:
                idx = mi
            else:
                lo = mi
        return (pos, idx)

    def _loc_right(self, value):
        """"""
        if not self._len:
            return (0, 0)
        _lists = self._lists
        _mins = self._mins
        (pos, hi) = (0, len(_lists))
        while pos + 1 < hi:
            mi = pos + hi >> 1
            if value < _mins[mi]:
                hi = mi
            else:
                pos = mi
        _list = _lists[pos]
        (lo, idx) = (-1, len(_list))
        while lo + 1 < idx:
            mi = lo + idx >> 1
            if value < _list[mi]:
                idx = mi
            else:
                lo = mi
        return (pos, idx)

    def _prev_interval(self, pos, idx):
        _lists = self._lists
        if idx < 0 or pos < 0:
            raise ValueError('idx or pos < 0 ', (idx, pos))
        if idx > 0:
            return (pos, idx - 1, _lists[pos][idx - 1])
        if pos > 0:
            last = self._list_lens[pos - 1] - 1
            return (pos - 1, last, _lists[pos - 1][last])
        return (-1, -1, None)

    def _next_interval(self, pos, idx):
        _lists = self._lists
        _list_lens = self._list_lens
        if idx < 0 or pos < 0:
            raise ValueError('idx or pos < 0 ', (idx, pos))
        if idx < _list_lens[pos] - 1:
            return (pos, idx + 1, _lists[pos][idx + 1])
        if pos < len(_lists) - 1:
            return (pos + 1, 0, _lists[pos + 1][0])
        return (-1, -1, None)

    def _insert(self, pos, idx, l, r):
        _load = self._load
        _lists = self._lists
        _mins = self._mins
        _list_lens = self._list_lens
        if _lists:
            _list = _lists[pos]
            self._fen_update(pos, 1)
            _list.insert(idx, Interval(l, r))
            _list_lens[pos] += 1
            _mins[pos] = _list[0]
            if _load + _load < len(_list):
                _lists.insert(pos + 1, _list[_load:])
                _list_lens.insert(pos + 1, len(_list) - _load)
                _mins.insert(pos + 1, _list[_load])
                _list_lens[pos] = _load
                del _list[_load:]
                self._rebuild = True
        else:
            itv = Interval(l, r)
            _lists.append([itv])
            _mins.append(itv)
            _list_lens.append(1)
            self._rebuild = True
        self._len += 1

    def get_left_interval(self, position):
        (pos, idx) = self._loc_right(Interval(position, position))
        (prev_pos, prev_idx, prev_itv) = self._prev_interval(pos, idx)
        if prev_itv is not None:
            return (prev_pos, prev_idx, prev_itv)
        return (-1, -1, None)

    def get_right_interval(self, position):
        (prev_pos, prev_idx, prev_itv) = self.get_left_interval(position)
        if prev_itv is not None:
            if position <= prev_itv.r:
                return (prev_pos, prev_idx, prev_itv)
            else:
                return self._next_interval(prev_pos, prev_idx)
        if self._lists:
            return (0, 0, self._lists[0][0])
        return (-1, -1, None)

    def add(self, l, r):
        _load = self._load
        _lists = self._lists
        _mins = self._mins
        _list_lens = self._list_lens
        if not _lists:
            self._insert(0, 0, l, r)
        (pos, idx) = self._loc_right(Interval(l, r))
        (prev_pos, prev_idx, prev_itv) = self._prev_interval(pos, idx)
        in_left = False
        if prev_itv is not None and l <= prev_itv.r:
            if r <= prev_itv.r:
                return
            in_left = True
        in_right = False
        rem = []
        (nxt_pos, nxt_idx, nxt_itv) = self._next_interval(prev_pos, prev_idx) if prev_itv is not None else (0, 0, self._lists[0][0])
        while nxt_itv is not None and r >= nxt_itv.r:
            rem.append((nxt_pos, nxt_idx))
            (nxt_pos, nxt_idx, nxt_itv) = self._next_interval(nxt_pos, nxt_idx)
        for (rem_pos, rem_idx) in reversed(rem):
            self._delete(rem_pos, rem_idx)
        if nxt_itv is not None and nxt_itv.l <= r:
            in_right = True
        if not in_left and (not in_right):
            self._insert(pos, idx, l, r)
        elif in_left and (not in_right):
            prev_itv.r = r
        elif not in_left and in_right:
            nxt_itv.l = l
        else:
            nxt_itv.l = prev_itv.l
            self._delete(prev_pos, prev_idx)

    def discard(self, l, r):
        _load = self._load
        _lists = self._lists
        _mins = self._mins
        _list_lens = self._list_lens
        if _lists:
            (pos, idx) = self._loc_right(Interval(l, r))
            (prev_pos, prev_idx, prev_itv) = self._prev_interval(pos, idx)
            in_left = False
            in_right = False
            if prev_itv is not None:
                if prev_itv.l < l < prev_itv.r:
                    in_left = True
                if prev_itv.l < r < prev_itv.r:
                    in_right = True
            else:
                (prev_pos, prev_idx, prev_itv) = (pos, idx, _lists[pos][idx])
            rem = []
            (nxt_pos, nxt_idx, nxt_itv) = (prev_pos, prev_idx, prev_itv)
            while nxt_itv is not None and nxt_itv.r <= r:
                if l <= nxt_itv.l:
                    rem.append((nxt_pos, nxt_idx))
                (nxt_pos, nxt_idx, nxt_itv) = self._next_interval(nxt_pos, nxt_idx)
            for (rem_pos, rem_idx) in reversed(rem):
                self._delete(rem_pos, rem_idx)
            if in_left and in_right:
                if l != r:
                    self._insert(pos, idx, r, prev_itv.r)
                    prev_itv.r = l
                return
            elif in_left:
                prev_itv.r = l
            if nxt_itv is not None and nxt_itv.l < r < nxt_itv.r:
                nxt_itv.l = r

    def pop(self, index=-1):
        """"""
        (pos, idx) = self._fen_findkth(self._len + index if index < 0 else index)
        value = self._lists[pos][idx]
        self._delete(pos, idx)
        return value

    def bisect_left(self, value):
        """"""
        (pos, idx) = self._loc_left(value)
        return self._fen_query(pos) + idx

    def bisect_right(self, value):
        """"""
        (pos, idx) = self._loc_right(value)
        return self._fen_query(pos) + idx

    def count(self, value):
        """"""
        return self.bisect_right(value) - self.bisect_left(value)

    def __len__(self):
        """"""
        return self._len

    def __getitem__(self, index):
        """"""
        (pos, idx) = self._fen_findkth(self._len + index if index < 0 else index)
        return self._lists[pos][idx]

    def __delitem__(self, index):
        """"""
        (pos, idx) = self._fen_findkth(self._len + index if index < 0 else index)
        self._delete(pos, idx)

    def __contains__(self, value):
        """"""
        _lists = self._lists
        if _lists:
            (pos, idx) = self._loc_left(value)
            return idx < len(_lists[pos]) and _lists[pos][idx] == value
        return False

    def __iter__(self):
        """"""
        return (value for _list in self._lists for value in _list)

    def __reversed__(self):
        """"""
        return (value for _list in reversed(self._lists) for value in reversed(_list))

    def __repr__(self):
        """"""
        return '[' + ', '.join((str(itvl) for itvl in list(self))) + ']'

class Interval:

    def __init__(self, l, r):
        self.l = l
        self.r = r

    def __str__(self):
        return '(' + str(self.l) + ', ' + str(self.r) + ')'

    def __repr__(self):
        return self.__str__()

    def __eq__(self, other):
        return self.l == other.l and self.r == other.r

    def __lt__(self, other):
        return self.l < other.l

    def __le__(self, other):
        return self.l <= other.l

def rem(il, val):
    (pos, idx, itv) = il.get_right_interval(val)
    if itv is not None and val >= itv.l:
        il.discard(floor(val), floor(val) + 1)
    else:
        left = itv.l
        il.add(floor(val), left)
        il.discard(left, left + 1)

def add(il, val):
    (pos, idx, itv) = il.get_left_interval(val)
    if itv is not None and val <= itv.r:
        right = itv.r
        il.discard(floor(val), right)
        il.add(right, right + 1)
    else:
        il.add(floor(val), floor(val) + 1)

def solve():
    res = []
    il = IntervalList([], 200)
    for val in A:
        add(il, val + 0.5)
    for _ in range(Q):
        (idx, val) = ti()
        idx -= 1
        rem(il, A[idx] + 0.5)
        A[idx] = val
        add(il, val + 0.5)
        res.append(il[-1].r - 1)
    return '\n'.join((str(v) for v in res))
for test in range(1, 1 + 1):
    (N, Q) = ti()
    A = li()
    print(solve())
file.close()