The Great Equalizer
Tema bought an old device with a small screen and a worn-out inscription "The Great Equalizer" on the side.The seller said that the device needs to be given an array $$$a$$$ of integers as input, after which "The Great Equalizer" will work as follows:   Sort the current array in non-decreasing order and remove duplicate elements leaving only one occurrence of each element.  If the current length of the array is equal to $$$1$$$, the device stops working and outputs the single number in the array — output value of the device.  Add an arithmetic progression {$$$n,\ n - 1,\ n - 2,\ \ldots,\ 1$$$} to the current array, where $$$n$$$ is the length of the current array. In other words, $$$n - i$$$ is added to the $$$i$$$-th element of the array, when indexed from zero.  Go to the first step. To test the operation of the device, Tema came up with a certain array of integers $$$a$$$, and then wanted to perform $$$q$$$ operations on the array $$$a$$$ of the following type:   Assign the value $$$x$$$ ($$$1 \le x \le 10^9$$$) to the element $$$a_i$$$ ($$$1 \le i \le n$$$).  Give the array $$$a$$$ as input to the device and find out the result of the device's operation, while the array $$$a$$$ remains unchanged during the operation of the device. Help Tema find out the output values of the device after each operation.
Let's consider the first example of the input.Initially, the array of numbers given as input to the device will be $$$[6, 4, 8]$$$. It will change as follows: $$$$$$[6, 4, 8] \rightarrow [4, 6, 8] \rightarrow [7, 8, 9] \rightarrow [10, 10, 10] \rightarrow [10]$$$$$$Then, the array of numbers given as input to the device will be $$$[6, 10, 8]$$$. It will change as follows: $$$$$$[6, 10, 8] \rightarrow [6, 8, 10] \rightarrow [9, 10, 11] \rightarrow [12, 12, 12] \rightarrow [12]$$$$$$The last array of numbers given as input to the device will be $$$[6, 10, 1]$$$. It will change as follows: $$$$$$[6, 10, 1] \rightarrow [1, 6, 10] \rightarrow [4, 8, 11] \rightarrow [7, 10, 12] \rightarrow [10, 12, 13] \rightarrow [13, 14, 14] \rightarrow [13, 14] \rightarrow [15, 15] \rightarrow [15]$$$$$$
The first line of the input contains a single integer $$$t$$$ ($$$1 \le t \le 10^4$$$) — the number of test cases.Then follows the description of each test case.The first line of each test case contains a single integer $$$n$$$ ($$$1 \le n \le 2 \cdot 10^5$$$) — the size of the array $$$a$$$ that Tema initially came up with.The second line of each test case contains $$$n$$$ integers $$$a_1, a_2, a_3, \ldots, a_n$$$ ($$$1 \le a_i \le 10^9$$$) — the elements of the array $$$a$$$.The third line of a set contains a single integer $$$q$$$ ($$$1 \le q \le 2 \cdot 10^5$$$) — the number of operations.Each of the next $$$q$$$ lines of a test case contains two integers $$$i$$$ ($$$1 \le i \le n$$$) and $$$x$$$ ($$$1 \le x \le 10^9$$$) - the descriptions of the operations.It is guaranteed that the sum of the values of $$$n$$$ and the sum of the values of $$$q$$$ for all test cases do not exceed $$$2 \cdot 10^5$$$.
For each test case, output $$$q$$$ integers — the output values of the device after each operation.
""""""

def main():
    t = int(input())
    allans = []
    for _ in range(t):
        n = int(input())
        a = readIntArr()
        sl_a = SortedList(a)
        gaps_arr = []
        b = a.copy()
        b.sort()
        for i in range(1, n):
            gaps_arr.append(b[i] - b[i - 1])
        SS = SpecialStructure(gaps_arr)
        q = int(input())
        ans = []
        for __ in range(q):
            (i, x) = readIntArr()
            i -= 1
            prev_x = a[i]
            removed_sl_a = []
            added_sl_a = []
            removed_gaps = []
            added_gaps = []
            i_a = sl_a.bisect_left(prev_x)
            removed_sl_a.append(prev_x)
            if i_a - 1 >= 0:
                removed_gaps.append(prev_x - sl_a[i_a - 1])
            if i_a + 1 < len(sl_a):
                removed_gaps.append(sl_a[i_a + 1] - prev_x)
            if i_a - 1 >= 0 and i_a + 1 < len(sl_a):
                added_gaps.append(sl_a[i_a + 1] - sl_a[i_a - 1])
            for z in removed_sl_a:
                sl_a.remove(z)
            for z in added_sl_a:
                sl_a.add(z)
            for z in removed_gaps:
                SS.remove(z)
            for z in added_gaps:
                SS.insert(z)
            removed_sl_a2 = []
            added_sl_a2 = []
            removed_gaps2 = []
            added_gaps2 = []
            i_a = sl_a.bisect_left(x)
            added_sl_a2.append(x)
            if i_a - 1 >= 0 and i_a < len(sl_a):
                removed_gaps2.append(sl_a[i_a] - sl_a[i_a - 1])
            if i_a - 1 >= 0:
                added_gaps2.append(x - sl_a[i_a - 1])
            if i_a < len(sl_a):
                added_gaps2.append(sl_a[i_a] - x)
            for z in removed_sl_a2:
                sl_a.remove(z)
            for z in added_sl_a2:
                sl_a.add(z)
            for z in removed_gaps2:
                SS.remove(z)
            for z in added_gaps2:
                SS.insert(z)
            v = sl_a[-1] + SS.get_largest()
            ans.append(v)
            a[i] = x
        allans.append(ans)
    multiLineArrayOfArraysPrint(allans)
    return
import heapq
from collections import Counter

class SpecialStructure:
    """"""

    def __init__(self, arr):
        self.h = [-x for x in arr]
        heapq.heapify(self.h)
        self.delayed_removal = Counter()

    def insert(self, x):
        heapq.heappush(self.h, -x)

    def remove(self, x):
        self.delayed_removal[-x] += 1

    def get_largest(self):
        while len(self.h) > 0 and self.delayed_removal[self.h[0]] > 0:
            self.delayed_removal[self.h[0]] -= 1
            heapq.heappop(self.h)
        if len(self.h) > 0:
            return -self.h[0]
        else:
            return 0

class SortedList:

    def __init__(self, iterable=[], _load=200):
        """"""
        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 add(self, value):
        """"""
        _load = self._load
        _lists = self._lists
        _mins = self._mins
        _list_lens = self._list_lens
        self._len += 1
        if _lists:
            (pos, idx) = self._loc_right(value)
            self._fen_update(pos, 1)
            _list = _lists[pos]
            _list.insert(idx, value)
            _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:
            _lists.append([value])
            _mins.append(value)
            _list_lens.append(1)
            self._rebuild = True

    def discard(self, value):
        """"""
        _lists = self._lists
        if _lists:
            (pos, idx) = self._loc_right(value)
            if idx and _lists[pos][idx - 1] == value:
                self._delete(pos, idx - 1)

    def remove(self, value):
        """"""
        _len = self._len
        self.discard(value)
        if _len == self._len:
            raise ValueError('{0!r} not in list'.format(value))

    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 'SortedList({0})'.format(list(self))

class OrderedList(SortedList):

    def __init__(self, arg):
        super().__init__(arg)

    def rangeCountByValue(self, leftVal, rightVal):
        leftCummulative = self.bisect_left(leftVal)
        rightCummulative = self.bisect_left(rightVal + 1)
        return rightCummulative - leftCummulative
import sys
input = sys.stdin.buffer.readline

def oneLineArrayPrint(arr):
    print(' '.join([str(x) for x in arr]))

def multiLineArrayPrint(arr):
    print('\n'.join([str(x) for x in arr]))

def multiLineArrayOfArraysPrint(arr):
    print('\n'.join([' '.join([str(x) for x in y]) for y in arr]))

def readIntArr():
    return [int(x) for x in input().split()]

def makeArr(defaultValFactory, dimensionArr):
    dv = defaultValFactory
    da = dimensionArr
    if len(da) == 1:
        return [dv() for _ in range(da[0])]
    else:
        return [makeArr(dv, da[1:]) for _ in range(da[0])]

def queryInteractive(a, b):
    print('? {} {}'.format(a, b))
    sys.stdout.flush()
    return int(input())

def answerInteractive(ans):
    print('! {}'.format(ans))
    sys.stdout.flush()
inf = float('inf')
from math import gcd, floor, ceil
import math
for _abc in range(1):
    main()
import random
import sys, os, io
input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline

def f(u, v):
    return u * m + v

def update(i, x, tree):
    i += l1
    tree[i] = x
    i >>= 1
    while i:
        tree[i] = max(tree[2 * i], tree[2 * i + 1])
        i >>= 1
    return

def left_max(r, tree):
    (s, t) = (l1, r + l1)
    while s <= t:
        if not t & 1:
            if tree[t]:
                while t < l1:
                    t = t << 1 ^ 1 if tree[t << 1 ^ 1] else t << 1
                return t ^ l1
            t -= 1
        s >>= 1
        t >>= 1
    return -1

def right_min(l, tree):
    (s, t) = (l + l1, l2 - 1)
    while s <= t:
        if s & 1:
            if tree[s]:
                while s < l1:
                    s = s << 1 if tree[s << 1] else s << 1 ^ 1
                return s ^ l1
            s += 1
        s >>= 1
        t >>= 1
    return -1
t = int(input())
ans = []
r = random.randint(1, pow(2, 30) - 1)
for _ in range(t):
    n = int(input())
    a = [0] + list(map(int, input().split()))
    l1 = pow(2, (n + 1).bit_length())
    l2 = 2 * l1
    tree = [0] * l2
    for i in range(1, n + 1):
        tree[i + l1] = a[i]
    for i in range(l1 - 1, 0, -1):
        tree[i] = max(tree[2 * i], tree[2 * i + 1])
    q = int(input())
    ans0 = [0] * q
    (i0, x0) = ([0] * q, [0] * q)
    for i in range(q):
        (j, x) = map(int, input().split())
        (i0[i], x0[i]) = (j, x)
        update(j, x, tree)
        ans0[i] = tree[1]
    u = a + x0
    v = [0]
    for i in sorted(u):
        if v[-1] ^ i:
            v.append(i)
    m = len(v)
    d = dict()
    for i in range(m):
        d[v[i] ^ r] = i
    cnt = [0] * m
    for i in a[1:]:
        cnt[d[i ^ r]] += 1
    l1 = pow(2, (m + 1).bit_length())
    l2 = 2 * l1
    tree1 = [0] * l2
    tree2 = [0] * l2
    la = 0
    for i in range(m):
        if cnt[i]:
            tree1[i + l1] = 1
            if la:
                tree2[la + l1] = v[i] - v[la]
            la = i
    for i in range(l1 - 1, 0, -1):
        tree1[i] = max(tree1[2 * i], tree1[2 * i + 1])
    for i in range(l1 - 1, 0, -1):
        tree2[i] = max(tree2[2 * i], tree2[2 * i + 1])
    for j in range(q):
        (i, x) = (i0[j], x0[j])
        k = d[a[i] ^ r]
        cnt[k] -= 1
        if not cnt[k]:
            update(k, 0, tree1)
            update(k, 0, tree2)
            l0 = left_max(k - 1, tree1)
            if l0 ^ -1:
                r0 = right_min(k + 1, tree1)
                if r0 ^ -1:
                    update(l0, v[r0] - v[l0], tree2)
                else:
                    update(l0, 0, tree2)
        k = d[x ^ r]
        cnt[k] += 1
        a[i] = x
        if cnt[k] == 1:
            l0 = left_max(k - 1, tree1)
            r0 = right_min(k + 1, tree1)
            update(k, 1, tree1)
            if l0 ^ -1:
                update(l0, v[k] - v[l0], tree2)
            if r0 ^ -1:
                update(k, v[r0] - v[k], tree2)
        ans0[j] += tree2[1]
    ans.append(' '.join(map(str, ans0)))
sys.stdout.write('\n'.join(ans))
""""""

def main():
    t = int(input())
    allans = []
    for _ in range(t):
        n = int(input())
        a = readIntArr()
        sl_a = SortedList(a)
        sl_gaps_arr = []
        b = a.copy()
        b.sort()
        for i in range(1, n):
            sl_gaps_arr.append(b[i] - b[i - 1])
        sl_gaps = SortedList(sl_gaps_arr)
        q = int(input())
        ans = []
        for __ in range(q):
            (i, x) = readIntArr()
            i -= 1
            prev_x = a[i]
            removed_sl_a = []
            added_sl_a = []
            removed_sl_gaps = []
            added_sl_gaps = []
            i_a = sl_a.bisect_left(prev_x)
            removed_sl_a.append(prev_x)
            if i_a - 1 >= 0:
                removed_sl_gaps.append(prev_x - sl_a[i_a - 1])
            if i_a + 1 < len(sl_a):
                removed_sl_gaps.append(sl_a[i_a + 1] - prev_x)
            if i_a - 1 >= 0 and i_a + 1 < len(sl_a):
                added_sl_gaps.append(sl_a[i_a + 1] - sl_a[i_a - 1])
            for z in removed_sl_a:
                sl_a.remove(z)
            for z in added_sl_a:
                sl_a.add(z)
            for z in removed_sl_gaps:
                sl_gaps.remove(z)
            for z in added_sl_gaps:
                sl_gaps.add(z)
            removed_sl_a2 = []
            added_sl_a2 = []
            removed_sl_gaps2 = []
            added_sl_gaps2 = []
            i_a = sl_a.bisect_left(x)
            added_sl_a2.append(x)
            if i_a - 1 >= 0 and i_a < len(sl_a):
                removed_sl_gaps2.append(sl_a[i_a] - sl_a[i_a - 1])
            if i_a - 1 >= 0:
                added_sl_gaps2.append(x - sl_a[i_a - 1])
            if i_a < len(sl_a):
                added_sl_gaps2.append(sl_a[i_a] - x)
            for z in removed_sl_a2:
                sl_a.remove(z)
            for z in added_sl_a2:
                sl_a.add(z)
            for z in removed_sl_gaps2:
                sl_gaps.remove(z)
            for z in added_sl_gaps2:
                sl_gaps.add(z)
            v = sl_a[-1]
            if len(sl_gaps) > 0:
                v += sl_gaps[-1]
            ans.append(v)
            a[i] = x
        allans.append(ans)
    multiLineArrayOfArraysPrint(allans)
    return

class SortedList:

    def __init__(self, iterable=[], _load=200):
        """"""
        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 add(self, value):
        """"""
        _load = self._load
        _lists = self._lists
        _mins = self._mins
        _list_lens = self._list_lens
        self._len += 1
        if _lists:
            (pos, idx) = self._loc_right(value)
            self._fen_update(pos, 1)
            _list = _lists[pos]
            _list.insert(idx, value)
            _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:
            _lists.append([value])
            _mins.append(value)
            _list_lens.append(1)
            self._rebuild = True

    def discard(self, value):
        """"""
        _lists = self._lists
        if _lists:
            (pos, idx) = self._loc_right(value)
            if idx and _lists[pos][idx - 1] == value:
                self._delete(pos, idx - 1)

    def remove(self, value):
        """"""
        _len = self._len
        self.discard(value)
        if _len == self._len:
            raise ValueError('{0!r} not in list'.format(value))

    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 'SortedList({0})'.format(list(self))

class OrderedList(SortedList):

    def __init__(self, arg):
        super().__init__(arg)

    def rangeCountByValue(self, leftVal, rightVal):
        leftCummulative = self.bisect_left(leftVal)
        rightCummulative = self.bisect_left(rightVal + 1)
        return rightCummulative - leftCummulative
import sys
input = sys.stdin.buffer.readline

def oneLineArrayPrint(arr):
    print(' '.join([str(x) for x in arr]))

def multiLineArrayPrint(arr):
    print('\n'.join([str(x) for x in arr]))

def multiLineArrayOfArraysPrint(arr):
    print('\n'.join([' '.join([str(x) for x in y]) for y in arr]))

def readIntArr():
    return [int(x) for x in input().split()]

def makeArr(defaultValFactory, dimensionArr):
    dv = defaultValFactory
    da = dimensionArr
    if len(da) == 1:
        return [dv() for _ in range(da[0])]
    else:
        return [makeArr(dv, da[1:]) for _ in range(da[0])]

def queryInteractive(a, b):
    print('? {} {}'.format(a, b))
    sys.stdout.flush()
    return int(input())

def answerInteractive(ans):
    print('! {}'.format(ans))
    sys.stdout.flush()
inf = float('inf')
from math import gcd, floor, ceil
import math
for _abc in range(1):
    main()