Vova decided to clean his room. The room can be represented as the coordinate axis $OX$. There are $n$ piles of trash in the room, coordinate of the $i$-th pile is the integer $p_i$. All piles have different coordinates.

Let's define a total cleanup as the following process. The goal of this process is to collect all the piles in no more than two different $x$ coordinates. To achieve this goal, Vova can do several (possibly, zero) moves. During one move, he can choose some $x$ and move all piles from $x$ to $x+1$ or $x-1$ using his broom. Note that he can't choose how many piles he will move.

Also, there are two types of queries:

  $0$ $x$ — remove a pile of trash from the coordinate $x$. It is guaranteed that there is a pile in the coordinate $x$ at this moment.  $1$ $x$ — add a pile of trash to the coordinate $x$. It is guaranteed that there is no pile in the coordinate $x$ at this moment. 

Note that it is possible that there are zero piles of trash in the room at some moment.

Vova wants to know the minimum number of moves he can spend if he wants to do a total cleanup before any queries. He also wants to know this number of moves after applying each query. Queries are applied in the given order. Note that the total cleanup doesn't actually happen and doesn't change the state of piles. It is only used to calculate the number of moves.

For better understanding, please read the Notes section below to see an explanation for the first example.


-----Input-----

The first line of the input contains two integers $n$ and $q$ ($1 \le n, q \le 10^5$) — the number of piles in the room before all queries and the number of queries, respectively.

The second line of the input contains $n$ distinct integers $p_1, p_2, \dots, p_n$ ($1 \le p_i \le 10^9$), where $p_i$ is the coordinate of the $i$-th pile.

The next $q$ lines describe queries. The $i$-th query is described with two integers $t_i$ and $x_i$ ($0 \le t_i \le 1; 1 \le x_i \le 10^9$), where $t_i$ is $0$ if you need to remove a pile from the coordinate $x_i$ and is $1$ if you need to add a pile to the coordinate $x_i$. It is guaranteed that for $t_i = 0$ there is such pile in the current set of piles and for $t_i = 1$ there is no such pile in the current set of piles.


-----Output-----

Print $q+1$ integers: the minimum number of moves Vova needs to do a total cleanup before the first query and after each of $q$ queries.


-----Examples-----
Input
5 6
1 2 6 8 10
1 4
1 9
0 6
0 10
1 100
1 50

Output
5
7
7
5
4
8
49

Input
5 8
5 1 2 4 3
0 1
0 2
0 3
0 4
0 5
1 1000000000
1 1
1 500000000

Output
3
2
1
0
0
0
0
0
499999999



-----Note-----

Consider the first example.

Initially, the set of piles is $[1, 2, 6, 8, 10]$. The answer before the first query is $5$ because you can move all piles from $1$ to $2$ with one move, all piles from $10$ to $8$ with $2$ moves and all piles from $6$ to $8$ with $2$ moves.

After the first query, the set becomes $[1, 2, 4, 6, 8, 10]$. Then the answer is $7$ because you can move all piles from $6$ to $4$ with $2$ moves, all piles from $4$ to $2$ with $2$ moves, all piles from $2$ to $1$ with $1$ move and all piles from $10$ to $8$ with $2$ moves.

After the second query, the set of piles becomes $[1, 2, 4, 6, 8, 9, 10]$ and the answer is the same (and the previous sequence of moves can be applied to the current set of piles).

After the third query, the set of piles becomes $[1, 2, 4, 8, 9, 10]$ and the answer is $5$ because you can move all piles from $1$ to $2$ with $1$ move, all piles from $2$ to $4$ with $2$ moves, all piles from $10$ to $9$ with $1$ move and all piles from $9$ to $8$ with $1$ move.

After the fourth query, the set becomes $[1, 2, 4, 8, 9]$ and the answer is almost the same (the previous sequence of moves can be applied without moving piles from $10$).

After the fifth query, the set becomes $[1, 2, 4, 8, 9, 100]$. You can move all piles from $1$ and further to $9$ and keep $100$ at its place. So the answer is $8$.

After the sixth query, the set becomes $[1, 2, 4, 8, 9, 50, 100]$. The answer is $49$ and can be obtained with almost the same sequence of moves as after the previous query. The only difference is that you need to move all piles from $50$ to $9$ too.

Source: codeforces | Difficulty: MEDIUM


Solutions:
from __future__ import division, print_function
from fractions import Fraction
import sys
import os
from io import BytesIO, IOBase
from bisect import bisect_left as bl
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')

def print(*args, **kwargs):
	(sep, file) = (kwargs.pop('sep', ' '), kwargs.pop('file', sys.stdout))
	at_start = True
	for x in args:
		if not at_start:
			file.write(sep)
		file.write(str(x))
		at_start = False
	file.write(kwargs.pop('end', '\n'))
	if kwargs.pop('flush', False):
		file.flush()
if sys.version_info[0] < 3:
	(sys.stdin, sys.stdout) = (FastIO(sys.stdin), FastIO(sys.stdout))
else:
	(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
from types import GeneratorType

def iterative(f, stack=[]):

	def wrapped_func(*args, **kwargs):
		if stack:
			return f(*args, **kwargs)
		to = f(*args, **kwargs)
		while True:
			if type(to) is GeneratorType:
				stack.append(to)
				to = next(to)
				continue
			stack.pop()
			if not stack:
				break
			to = stack[-1].send(to)
		return to
	return wrapped_func
mod = 1000000007

def inp():
	return sys.stdin.readline().rstrip('\r\n')

def out(var):
	sys.stdout.write(str(var))

def lis():
	return list(map(int, inp().split()))

def stringlis():
	return list(map(str, inp().split()))

def sep():
	return map(int, inp().split())

def strsep():
	return map(str, inp().split())

def zerolist(n):
	return [0] * n

def nextline():
	out('\n')

def testcase(t):
	for pp in range(t):
		solve(pp)

def printlist(a):
	for p in range(0, len(a)):
		out(str(a[p]) + ' ')

def google(p):
	print('Case #' + str(p) + ': ', end='')

def lcm(a, b):
	return a * b // gcd(a, b)

def power(x, y, p):
	res = 1
	x = x % p
	if x == 0:
		return 0
	while y > 0:
		if y & 1 == 1:
			res = res * x % p
		y = y >> 1
		x = x * x % p
	return res

def ncr(n, r):
	return factorial(n) // (factorial(r) * factorial(max(n - r, 1)))

def isPrime(n):
	if n <= 1:
		return False
	if n <= 3:
		return True
	if n % 2 == 0 or n % 3 == 0:
		return False
	i = 5
	while i * i <= n:
		if n % i == 0 or n % (i + 2) == 0:
			return False
		i = i + 6
	return True

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))

def ans(sl, gap):
	if len(sl) < 3:
		print(0)
		return
	print(sl[len(sl) - 1] - sl[0] - gap[len(gap) - 1])

def solve(case):
	(n, q) = sep()
	a = lis()
	sl = SortedList(a)
	gep = []
	for i in range(1, len(sl)):
		gep.append(sl[i] - sl[i - 1])
	gap = SortedList(gep)
	ans(sl, gap)
	for ii in range(q):
		(x, y) = sep()
		if x == 1:
			ind = bl(sl, y)
			if len(sl) > 0:
				if ind == len(sl):
					gap.add(y - sl[ind - 1])
				elif ind == 0:
					gap.add(sl[ind] - y)
				else:
					gap.remove(sl[ind] - sl[ind - 1])
					gap.add(sl[ind] - y)
					gap.add(y - sl[ind - 1])
			sl.add(y)
			ans(sl, gap)
		else:
			ind = bl(sl, y)
			if ind != len(sl) - 1:
				gap.remove(sl[ind + 1] - sl[ind])
			if ind > 0:
				gap.remove(sl[ind] - sl[ind - 1])
			if ind < len(sl) - 1 and ind > 0:
				gap.add(sl[ind + 1] - sl[ind - 1])
			sl.remove(y)
			ans(sl, gap)
testcase(1)


import sys

def minp():
	return sys.stdin.readline().strip()

def mint():
	return int(minp())

def mints():
	return map(int, minp().split())

def get(t, l, r):
	l += len(t) // 2
	r += len(t) // 2
	res = -1
	while l <= r:
		if l % 2 == 1:
			res = max(res, t[l])
		if r % 2 == 0:
			res = max(res, t[r])
		l = (l + 1) // 2
		r = (r - 1) // 2
	return res

def change(t, x, v):
	x += len(t) // 2
	t[x] = v
	while x > 1:
		x //= 2
		t[x] = max(t[x * 2], t[x * 2 + 1])

def build(t):
	for x in range(len(t) // 2 - 1, 0, -1):
		t[x] = max(t[x * 2], t[x * 2 + 1])

def solve():
	(n, q) = mints()
	p = list(mints())
	all_x = p[:]
	qe = [None] * q
	for i in range(q):
		(t, x) = mints()
		qe[i] = (t, x)
		all_x.append(x)
	all_x.append(0)
	all_x.append(int(1000000000.0) + 1)
	all_x.sort()
	id_x = dict()
	allx = []
	idn = 0
	for i in all_x:
		if i not in id_x:
			id_x[i] = idn
			idn += 1
			allx.append(i)
	m = idn
	nnext = [-1] * m
	pprev = [-1] * m
	z = [0] * m
	nnext[0] = m - 1
	pprev[m - 1] = 0
	have = [-1] * (m * 2)
	have[m - 1] = m - 1
	cnt = [0] * (m * 2)
	build(have)
	change(have, 0, 0)
	build(cnt)
	for x in set(p):
		xi = id_x[x]
		pr = get(have, 0, xi)
		nz = x - allx[pr]
		change(cnt, pr, nz)
		change(have, xi, xi)
		ne = nnext[pr]
		change(cnt, xi, allx[ne] - x)
		nnext[pr] = xi
		nnext[xi] = ne
		pprev[xi] = pr
		pprev[ne] = xi
	if nnext[0] == m - 1:
		print(0)
	else:
		ne = nnext[0]
		pr = pprev[m - 1]
		if ne == pr:
			print(0)
		else:
			print(allx[pr] - allx[ne] - get(cnt, ne, pr - 1))
	for (t, x) in qe:
		xi = id_x[x]
		if t == 0:
			ne = nnext[xi]
			pr = pprev[xi]
			change(have, xi, -1)
			change(cnt, xi, 0)
			change(cnt, pr, allx[ne] - allx[pr])
			nnext[pr] = ne
			pprev[ne] = pr
		else:
			pr = get(have, 0, xi)
			nz = x - allx[pr]
			change(cnt, pr, nz)
			change(have, xi, xi)
			ne = nnext[pr]
			change(cnt, xi, allx[ne] - x)
			nnext[pr] = xi
			nnext[xi] = ne
			pprev[xi] = pr
			pprev[ne] = xi
		if nnext[0] == m - 1:
			print(0)
		else:
			ne = nnext[0]
			pr = pprev[m - 1]
			if ne == pr:
				print(0)
			else:
				print(allx[pr] - allx[ne] - get(cnt, ne, pr - 1))
solve()


import os
import sys
from io import BytesIO, IOBase
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')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline()

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))

def RL():
	return map(int, sys.stdin.readline().split())

def RLL():
	return list(map(int, sys.stdin.readline().split()))

def N():
	return int(input())

def print_list(l):
	print(' '.join(map(str, l)))
import bisect as bs
data = [list(map(int, line.split())) for line in sys.stdin.readlines()]
(n, q) = data[0]
data[1].sort()
gap = [data[1][i] - data[1][i - 1] for i in range(1, len(data[1]))]
trash = SortedList(data[1])
gap = SortedList(gap)
(l, r) = (trash[0], trash[-1]) if trash else (0, 0)
m = gap[-1] if gap else 0
print(r - l - m)
for i in range(2, q + 2):
	(t, x) = data[i]
	if t == 1:
		p = bs.bisect_left(trash, x)
		if p > 0:
			gap.add(x - trash[p - 1])
		if p < len(trash):
			gap.add(trash[p] - x)
		if 0 < p < len(trash):
			gap.discard(trash[p] - trash[p - 1])
		trash.add(x)
	else:
		p = bs.bisect_left(trash, x)
		trash.discard(x)
		if p > 0:
			gap.discard(x - trash[p - 1])
		if p < len(trash):
			gap.discard(trash[p] - x)
		if 0 < p < len(trash):
			gap.add(trash[p] - trash[p - 1])
	(l, r) = (trash[0], trash[-1]) if trash else (0, 0)
	m = gap[-1] if gap else 0
	print(r - l - m)


import math
from sys import stdin, stdout

def getInts():
	return list(map(int, stdin.readline().strip().split()))

def getInt():
	return int(stdin.readline().strip())

def lower_bound(v, x):
	low = 0
	high = len(v) - 1
	ans = len(v)
	while low <= high:
		mid = (low + high) // 2
		if v[mid] < x:
			low = mid + 1
		else:
			ans = mid
			high = mid - 1
	return ans

def upper_bound(v, x):
	low = 0
	high = len(v) - 1
	ans = len(v)
	while low <= high:
		mid = (low + high) // 2
		if v[mid] <= x:
			low = mid + 1
		else:
			ans = mid
			high = mid - 1
	return ans
MOD = 1000000007

def mul(x, y):
	ans = x * y
	if ans > MOD:
		ans = ans % MOD
	if ans < 0:
		ans = ans % MOD
		ans = (ans + MOD) % MOD
	return ans

def add(x, y):
	ans = x + y
	if ans > MOD:
		ans = ans % MOD
	if ans < 0:
		ans = ans % MOD
		ans = (ans + MOD) % MOD
	return ans
import bisect

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))
(n, q) = getInts()
aa = getInts()
aa.sort()
gggap = []
for i in range(0, len(aa) - 1):
	gggap.append(aa[i] - aa[i + 1])
gggap.sort()
ans = []
if len(aa) <= 1:
	ans.append(0)
else:
	ans.append(aa[len(aa) - 1] - aa[0] + gggap[0])
a = SortedList(aa)
gap = SortedList(gggap)
for i in range(0, q):
	(x, y) = getInts()
	if x == 1:
		p = bisect.bisect_left(a, y)
		if p == 0 and len(a) > 0:
			qq = y - a[0]
			gap.add(qq)
		elif p == len(a) and len(a) > 0:
			qq = a[len(a) - 1] - y
			gap.add(qq)
		elif len(a) > 1:
			qq = a[p - 1] - a[p]
			gap.remove(qq)
			qq = a[p - 1] - y
			gap.add(qq)
			qq = y - a[p]
			gap.add(qq)
		a.add(y)
	else:
		p = bisect.bisect_left(a, y)
		if p == 0 and len(a) > 1:
			qq = y - a[1]
			gap.remove(qq)
		elif p == len(a) - 1 and len(a) > 1:
			qq = a[len(a) - 2] - y
			gap.remove(qq)
		elif len(a) > 2:
			qq = a[p - 1] - y
			gap.remove(qq)
			qq = y - a[p + 1]
			gap.remove(qq)
			qq = a[p - 1] - a[p + 1]
			gap.add(qq)
		a.remove(y)
	if len(a) <= 1:
		ans.append(0)
	else:
		ans1 = a[len(a) - 1] - a[0] + gap[0]
		ans.append(ans1)
for i in ans:
	stdout.write(str(i) + '\n')


from heapq import heappop, heappush
from collections import Counter
import sys
readline = sys.stdin.readline
INF = 1 << 60

def read_int():
	return int(readline())

def read_int_n():
	return list(map(int, readline().split()))

def read_float():
	return float(readline())

def read_float_n():
	return list(map(float, readline().split()))

def read_str():
	return readline().strip()

def read_str_n():
	return readline().strip().split()

def ep(*args):
	print(*args, file=sys.stderr)

def mt(f):
	import time

	def wrap(*args, **kwargs):
		s = time.perf_counter()
		ret = f(*args, **kwargs)
		e = time.perf_counter()
		ep(e - s, 'sec')
		return ret
	return wrap

class SegmentTree:

	def __init__(self, array, operator, identity_element):
		_len = len(array)
		self.__len = _len
		self.__op = operator
		self.__size = 1 << (_len - 1).bit_length()
		self.__tree = [identity_element] * self.__size + array + [identity_element] * (self.__size - _len)
		self.__ie = identity_element
		for i in range(self.__size - 1, 0, -1):
			self.__tree[i] = operator(self.__tree[i * 2], self.__tree[i * 2 + 1])

	def update(self, i, v):
		i += self.__size
		self.__tree[i] = v
		while i:
			i //= 2
			self.__tree[i] = self.__op(self.__tree[i * 2], self.__tree[i * 2 + 1])

	def query(self, l, r):
		l += self.__size
		r += self.__size
		ret = self.__ie
		while l < r:
			if l & 1:
				ret = self.__op(ret, self.__tree[l])
				l += 1
			if r & 1:
				r -= 1
				ret = self.__op(ret, self.__tree[r])
			l //= 2
			r //= 2
		return ret

	def max_right(self, l, f):
		assert 0 <= l <= self.__len
		if l == self.__len:
			return self.__len
		l += self.__size
		sm = self.__ie
		while True:
			while l % 2 == 0:
				l >>= 1
			if not f(self.__op(sm, self.__tree[l])):
				while l < self.__size:
					l = 2 * l
					if f(self.__op(sm, self.__tree[l])):
						sm = self.__op(sm, self.__tree[l])
						l += 1
				return l - self.__size
			sm = self.__op(sm, self.__tree[l])
			l += 1
			if l & -l == l:
				break
		return self.__len

	def min_left(self, r, f):
		assert 0 <= r <= self.__len
		if r == 0:
			return 0
		r += self.__size
		sm = self.__ie
		while True:
			r -= 1
			while r > 1 and r % 2:
				r >>= 1
			if not f(self.__op(sm, self.__tree[r])):
				while r < self.__size:
					r = 2 * r + 1
					if f(self.__op(sm, self.__tree[r])):
						sm = self.__op(sm, self.__tree[r])
						r -= 1
				return r + 1 - self.__size
			sm = self.__op(sm, self.__tree[r])
			if r & -r == r:
				break
		return 0

	def __getitem__(self, key):
		return self.__tree[key + self.__size]

class RemovableHeapQueue:

	def __init__(self):
		self.__q = []
		self.__cc = Counter()
		self.o = 10 ** 6

	def add(self, v, k):
		k = k[0] * self.o + k[1]
		heappush(self.__q, (v, k))
		self.__cc[k] += 1

	def remove(self, k):
		k = k[0] * self.o + k[1]
		self.__cc[k] -= 1
		assert self.__cc[k] >= 0

	def refrash(self):
		while self.__q:
			if self.__cc[self.__q[0][1]] == 0:
				heappop(self.__q)
			else:
				break

	def pop(self):
		self.refrash()
		return heappop(self.__q)

	def top(self):
		self.refrash()
		return self.__q[0]

	def empty(self):
		self.refrash()
		return len(self.__q) == 0

def slv(N, P, Q):
	p = P[:] + [x for (_, x) in Q]
	p.sort()
	p2i = {p: i for (i, p) in enumerate(p)}
	i2p = p
	M = len(i2p)
	lst = SegmentTree([-INF] * M, max, -INF)
	rst = SegmentTree([INF] * M, min, INF)
	for x in P:
		i = p2i[x]
		lst.update(i, i)
		rst.update(i, i)
	q = RemovableHeapQueue()
	P.sort()
	for i in range(len(P) - 1):
		d = P[i + 1] - P[i]
		(ai, bi) = (p2i[P[i]], p2i[P[i + 1]])
		q.add(-d, (ai, bi))

	def add(x):
		ci = p2i[x]
		ai = lst.query(0, ci)
		bi = rst.query(ci + 1, M)
		lst.update(ci, ci)
		rst.update(ci, ci)
		if ai != -INF:
			q.add(-(i2p[ci] - i2p[ai]), (ai, ci))
		if bi != INF:
			q.add(-(i2p[bi] - i2p[ci]), (ci, bi))
		if ai != -INF and bi != INF:
			q.remove((ai, bi))
		return q.top() if not q.empty() else (0, (None, None))

	def remove(x):
		ci = p2i[x]
		lst.update(ci, -INF)
		rst.update(ci, INF)
		ai = lst.query(0, ci)
		bi = rst.query(ci + 1, M)
		if ai != -INF:
			q.remove((ai, ci))
		if bi != INF:
			q.remove((ci, bi))
		if ai != -INF and bi != INF:
			q.add(-(i2p[bi] - i2p[ai]), (ai, bi))
		return q.top() if not q.empty() else (0, (None, None))
	if not q.empty():
		ans = [max(P) - min(P) + q.top()[0]]
	else:
		ans = [0]
	for (t, x) in Q:
		if t == 0:
			a = remove(x)
		else:
			a = add(x)
		li = lst.query(0, M)
		ri = rst.query(0, M)
		if li != -INF:
			l = i2p[li]
			r = i2p[ri]
			if l == r:
				ans.append(0)
			else:
				ans.append(l - r + a[0])
		else:
			ans.append(0)
	return ans

def main():
	(N, Q) = read_int_n()
	P = read_int_n()
	Q = [read_int_n() for _ in range(Q)]
	print(*slv(N, P, Q), sep='\n')
main()


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(list(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))
(n, q) = list(map(int, input().split()))
p = SortedList(list(map(int, input().split())))
gaps = SortedList()
for i in range(n - 1):
	gaps.add(p[i] - p[i + 1])
out = []

def ret(p, gaps):
	if len(p) > 1:
		out.append(p[len(p) - 1] - p[0] + gaps[0])
	else:
		out.append(0)
ret(p, gaps)
for i in range(q):
	(t, x) = list(map(int, input().split()))
	if t == 1:
		if len(p) > 0:
			ind = p.bisect_left(x)
			if ind == 0:
				gaps.add(x - p[0])
			elif ind == len(p):
				gaps.add(p[len(p) - 1] - x)
			else:
				gaps.remove(p[ind - 1] - p[ind])
				gaps.add(p[ind - 1] - x)
				gaps.add(x - p[ind])
		p.add(x)
	else:
		p.remove(x)
		if len(p) > 0:
			ind = p.bisect_left(x)
			if ind == 0:
				gaps.remove(x - p[0])
			elif ind == len(p):
				gaps.remove(p[len(p) - 1] - x)
			else:
				gaps.add(p[ind - 1] - p[ind])
				gaps.remove(p[ind - 1] - x)
				gaps.remove(x - p[ind])
	ret(p, gaps)
print('\n'.join(map(str, out)))


from bisect import bisect_right, bisect_left

class BITbisect:

	def __init__(self, InputProbNumbers):
		self.ind_to_co = [-10 ** 18]
		self.co_to_ind = {}
		for (ind, num) in enumerate(sorted(list(set(InputProbNumbers)))):
			self.ind_to_co.append(num)
			self.co_to_ind[num] = ind + 1
		self.max = len(self.co_to_ind)
		self.data = [0] * (self.max + 1)

	def __str__(self):
		retList = []
		for i in range(1, self.max + 1):
			x = self.ind_to_co[i]
			if self.count(x):
				c = self.count(x)
				for _ in range(c):
					retList.append(x)
		return '[' + ', '.join([str(a) for a in retList]) + ']'

	def __getitem__(self, key):
		key += 1
		s = 0
		ind = 0
		l = self.max.bit_length()
		for i in reversed(range(l)):
			if ind + (1 << i) <= self.max:
				if s + self.data[ind + (1 << i)] < key:
					s += self.data[ind + (1 << i)]
					ind += 1 << i
		if ind == self.max or key < 0:
			raise IndexError('BIT index out of range')
		return self.ind_to_co[ind + 1]

	def __len__(self):
		return self._query_sum(self.max)

	def __contains__(self, num):
		if not num in self.co_to_ind:
			return False
		return self.count(num) > 0

	def _query_sum(self, i):
		s = 0
		while i > 0:
			s += self.data[i]
			i -= i & -i
		return s

	def _add(self, i, x):
		while i <= self.max:
			self.data[i] += x
			i += i & -i

	def push(self, x):
		if not x in self.co_to_ind:
			raise KeyError('The pushing number didnt initialized')
		self._add(self.co_to_ind[x], 1)

	def delete(self, x):
		if not x in self.co_to_ind:
			raise KeyError('The deleting number didnt initialized')
		if self.count(x) <= 0:
			raise ValueError('The deleting number doesnt exist')
		self._add(self.co_to_ind[x], -1)

	def count(self, x):
		return self._query_sum(self.co_to_ind[x]) - self._query_sum(self.co_to_ind[x] - 1)

	def bisect_right(self, x):
		if x in self.co_to_ind:
			i = self.co_to_ind[x]
		else:
			i = bisect_right(self.ind_to_co, x) - 1
		return self._query_sum(i)

	def bisect_left(self, x):
		if x in self.co_to_ind:
			i = self.co_to_ind[x]
		else:
			i = bisect_left(self.ind_to_co, x)
		if i == 1:
			return 0
		return self._query_sum(i - 1)

def main():
	import sys
	input = sys.stdin.buffer.readline
	import heapq as hp
	(N, Q) = map(int, input().split())
	A = list(map(int, input().split()))
	A.sort()
	InputNum = A[:]
	Query = []
	for _ in range(Q):
		(a, b) = map(int, input().split())
		InputNum.append(b)
		Query.append((a, b))
	q = []
	for i in range(N - 1):
		hp.heappush(q, (-A[i + 1] + A[i], A[i], A[i + 1]))
	bit = BITbisect(InputNum)
	for a in A:
		bit.push(a)
	if q:
		print(A[-1] - A[0] + q[0][0])
	else:
		print(0)
	l = N
	for (a, b) in Query:
		ind = bit.bisect_left(b)
		m2 = bit[ind - 1] if 0 <= ind - 1 < l else -1
		if a == 1:
			m1 = bit[ind] if 0 <= ind < l else -1
			if m1 != -1:
				hp.heappush(q, (-m1 + b, b, m1))
			if m2 != -1:
				hp.heappush(q, (-b + m2, m2, b))
			bit.push(b)
			l += 1
		else:
			m0 = bit[ind + 1] if 0 <= ind + 1 < l else -1
			if m0 != -1 and m2 != -1:
				hp.heappush(q, (-m0 + m2, m2, m0))
			bit.delete(b)
			l -= 1
		while q:
			(d, s, t) = q[0]
			if not s in bit or not t in bit or bit.bisect_left(t) - bit.bisect_left(s) != 1:
				hp.heappop(q)
			else:
				break
		if l <= 2:
			ans = 0
		else:
			ans = bit[l - 1] - bit[0] + d
		print(ans)
main()


import bisect

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))
(n, q) = map(int, input().split())
a = list(map(int, input().split()))
a.sort()
gap = [a[i] - a[i - 1] for i in range(1, n)]
a = SortedList(a)
gap = SortedList(gap)
Q = []
u = a[-1] - a[0] if a else 0
v = gap[-1] if gap else 0
print(u - v)
for _ in range(q):
	Q.append(map(int, input().split()))
for (t, x) in Q:
	if t == 1:
		k = bisect.bisect_left(a, x)
		if k > 0:
			gap.add(x - a[k - 1])
		if k < len(a):
			gap.add(a[k] - x)
		if 0 < k < len(a):
			gap.discard(a[k] - a[k - 1])
		a.add(x)
	else:
		k = bisect.bisect_left(a, x)
		a.discard(x)
		if k > 0:
			gap.discard(x - a[k - 1])
		if k < len(a):
			gap.discard(a[k] - x)
		if 0 < k < len(a):
			gap.add(a[k] - a[k - 1])
	u = a[-1] - a[0] if a else 0
	v = gap[-1] if gap else 0
	print(u - v)


from __future__ import print_function
import sys
import traceback
from bisect import bisect_left, bisect_right, insort
from itertools import chain, repeat, starmap
from math import log
from operator import add, eq, ne, gt, ge, lt, le, iadd
from textwrap import dedent
try:
	from collections.abc import Sequence, MutableSequence
except ImportError:
	from collections import Sequence, MutableSequence
from functools import wraps
from sys import hexversion
if hexversion < 50331648:
	from itertools import imap as map
	from itertools import izip as zip
	try:
		from thread import get_ident
	except ImportError:
		from dummy_thread import get_ident
else:
	from functools import reduce
	try:
		from _thread import get_ident
	except ImportError:
		from _dummy_thread import get_ident

def recursive_repr(fillvalue='...'):

	def decorating_function(user_function):
		repr_running = set()

		@wraps(user_function)
		def wrapper(self):
			key = (id(self), get_ident())
			if key in repr_running:
				return fillvalue
			repr_running.add(key)
			try:
				result = user_function(self)
			finally:
				repr_running.discard(key)
			return result
		return wrapper
	return decorating_function

class SortedList(MutableSequence):
	DEFAULT_LOAD_FACTOR = 1000

	def __init__(self, iterable=None, key=None):
		assert key is None
		self._len = 0
		self._load = self.DEFAULT_LOAD_FACTOR
		self._lists = []
		self._maxes = []
		self._index = []
		self._offset = 0
		if iterable is not None:
			self._update(iterable)

	def __new__(cls, iterable=None, key=None):
		if key is None:
			return object.__new__(cls)
		elif cls is SortedList:
			return object.__new__(SortedKeyList)
		else:
			raise TypeError('inherit SortedKeyList for key argument')

	@property
	def key(self):
		return None

	def _reset(self, load):
		values = reduce(iadd, self._lists, [])
		self._clear()
		self._load = load
		self._update(values)

	def clear(self):
		self._len = 0
		del self._lists[:]
		del self._maxes[:]
		del self._index[:]
		self._offset = 0
	_clear = clear

	def add(self, value):
		_lists = self._lists
		_maxes = self._maxes
		if _maxes:
			pos = bisect_right(_maxes, value)
			if pos == len(_maxes):
				pos -= 1
				_lists[pos].append(value)
				_maxes[pos] = value
			else:
				insort(_lists[pos], value)
			self._expand(pos)
		else:
			_lists.append([value])
			_maxes.append(value)
		self._len += 1

	def _expand(self, pos):
		_load = self._load
		_lists = self._lists
		_index = self._index
		if len(_lists[pos]) > _load << 1:
			_maxes = self._maxes
			_lists_pos = _lists[pos]
			half = _lists_pos[_load:]
			del _lists_pos[_load:]
			_maxes[pos] = _lists_pos[-1]
			_lists.insert(pos + 1, half)
			_maxes.insert(pos + 1, half[-1])
			del _index[:]
		elif _index:
			child = self._offset + pos
			while child:
				_index[child] += 1
				child = child - 1 >> 1
			_index[0] += 1

	def update(self, iterable):
		_lists = self._lists
		_maxes = self._maxes
		values = sorted(iterable)
		if _maxes:
			if len(values) * 4 >= self._len:
				values.extend(chain.from_iterable(_lists))
				values.sort()
				self._clear()
			else:
				_add = self.add
				for val in values:
					_add(val)
				return
		_load = self._load
		_lists.extend((values[pos:pos + _load] for pos in range(0, len(values), _load)))
		_maxes.extend((sublist[-1] for sublist in _lists))
		self._len = len(values)
		del self._index[:]
	_update = update

	def __contains__(self, value):
		_maxes = self._maxes
		if not _maxes:
			return False
		pos = bisect_left(_maxes, value)
		if pos == len(_maxes):
			return False
		_lists = self._lists
		idx = bisect_left(_lists[pos], value)
		return _lists[pos][idx] == value

	def discard(self, value):
		_maxes = self._maxes
		if not _maxes:
			return
		pos = bisect_left(_maxes, value)
		if pos == len(_maxes):
			return
		_lists = self._lists
		idx = bisect_left(_lists[pos], value)
		if _lists[pos][idx] == value:
			self._delete(pos, idx)

	def remove(self, value):
		_maxes = self._maxes
		if not _maxes:
			raise ValueError('{0!r} not in list'.format(value))
		pos = bisect_left(_maxes, value)
		if pos == len(_maxes):
			raise ValueError('{0!r} not in list'.format(value))
		_lists = self._lists
		idx = bisect_left(_lists[pos], value)
		if _lists[pos][idx] == value:
			self._delete(pos, idx)
		else:
			raise ValueError('{0!r} not in list'.format(value))

	def _delete(self, pos, idx):
		_lists = self._lists
		_maxes = self._maxes
		_index = self._index
		_lists_pos = _lists[pos]
		del _lists_pos[idx]
		self._len -= 1
		len_lists_pos = len(_lists_pos)
		if len_lists_pos > self._load >> 1:
			_maxes[pos] = _lists_pos[-1]
			if _index:
				child = self._offset + pos
				while child > 0:
					_index[child] -= 1
					child = child - 1 >> 1
				_index[0] -= 1
		elif len(_lists) > 1:
			if not pos:
				pos += 1
			prev = pos - 1
			_lists[prev].extend(_lists[pos])
			_maxes[prev] = _lists[prev][-1]
			del _lists[pos]
			del _maxes[pos]
			del _index[:]
			self._expand(prev)
		elif len_lists_pos:
			_maxes[pos] = _lists_pos[-1]
		else:
			del _lists[pos]
			del _maxes[pos]
			del _index[:]

	def _loc(self, pos, idx):
		if not pos:
			return idx
		_index = self._index
		if not _index:
			self._build_index()
		total = 0
		pos += self._offset
		while pos:
			if not pos & 1:
				total += _index[pos - 1]
			pos = pos - 1 >> 1
		return total + idx

	def _pos(self, idx):
		if idx < 0:
			last_len = len(self._lists[-1])
			if -idx <= last_len:
				return (len(self._lists) - 1, last_len + idx)
			idx += self._len
			if idx < 0:
				raise IndexError('list index out of range')
		elif idx >= self._len:
			raise IndexError('list index out of range')
		if idx < len(self._lists[0]):
			return (0, idx)
		_index = self._index
		if not _index:
			self._build_index()
		pos = 0
		child = 1
		len_index = len(_index)
		while child < len_index:
			index_child = _index[child]
			if idx < index_child:
				pos = child
			else:
				idx -= index_child
				pos = child + 1
			child = (pos << 1) + 1
		return (pos - self._offset, idx)

	def _build_index(self):
		row0 = list(map(len, self._lists))
		if len(row0) == 1:
			self._index[:] = row0
			self._offset = 0
			return
		head = iter(row0)
		tail = iter(head)
		row1 = list(starmap(add, zip(head, tail)))
		if len(row0) & 1:
			row1.append(row0[-1])
		if len(row1) == 1:
			self._index[:] = row1 + row0
			self._offset = 1
			return
		size = 2 ** (int(log(len(row1) - 1, 2)) + 1)
		row1.extend(repeat(0, size - len(row1)))
		tree = [row0, row1]
		while len(tree[-1]) > 1:
			head = iter(tree[-1])
			tail = iter(head)
			row = list(starmap(add, zip(head, tail)))
			tree.append(row)
		reduce(iadd, reversed(tree), self._index)
		self._offset = size * 2 - 1

	def __delitem__(self, index):
		if isinstance(index, slice):
			(start, stop, step) = index.indices(self._len)
			if step == 1 and start < stop:
				if start == 0 and stop == self._len:
					return self._clear()
				elif self._len <= 8 * (stop - start):
					values = self._getitem(slice(None, start))
					if stop < self._len:
						values += self._getitem(slice(stop, None))
					self._clear()
					return self._update(values)
			indices = range(start, stop, step)
			if step > 0:
				indices = reversed(indices)
			(_pos, _delete) = (self._pos, self._delete)
			for index in indices:
				(pos, idx) = _pos(index)
				_delete(pos, idx)
		else:
			(pos, idx) = self._pos(index)
			self._delete(pos, idx)

	def __getitem__(self, index):
		_lists = self._lists
		if isinstance(index, slice):
			(start, stop, step) = index.indices(self._len)
			if step == 1 and start < stop:
				if start == 0 and stop == self._len:
					return reduce(iadd, self._lists, [])
				(start_pos, start_idx) = self._pos(start)
				start_list = _lists[start_pos]
				stop_idx = start_idx + stop - start
				if len(start_list) >= stop_idx:
					return start_list[start_idx:stop_idx]
				if stop == self._len:
					stop_pos = len(_lists) - 1
					stop_idx = len(_lists[stop_pos])
				else:
					(stop_pos, stop_idx) = self._pos(stop)
				prefix = _lists[start_pos][start_idx:]
				middle = _lists[start_pos + 1:stop_pos]
				result = reduce(iadd, middle, prefix)
				result += _lists[stop_pos][:stop_idx]
				return result
			if step == -1 and start > stop:
				result = self._getitem(slice(stop + 1, start + 1))
				result.reverse()
				return result
			indices = range(start, stop, step)
			return list((self._getitem(index) for index in indices))
		else:
			if self._len:
				if index == 0:
					return _lists[0][0]
				elif index == -1:
					return _lists[-1][-1]
			else:
				raise IndexError('list index out of range')
			if 0 <= index < len(_lists[0]):
				return _lists[0][index]
			len_last = len(_lists[-1])
			if -len_last < index < 0:
				return _lists[-1][len_last + index]
			(pos, idx) = self._pos(index)
			return _lists[pos][idx]
	_getitem = __getitem__

	def __setitem__(self, index, value):
		message = 'use ``del sl[index]`` and ``sl.add(value)`` instead'
		raise NotImplementedError(message)

	def __iter__(self):
		return chain.from_iterable(self._lists)

	def __reversed__(self):
		return chain.from_iterable(map(reversed, reversed(self._lists)))

	def reverse(self):
		raise NotImplementedError('use ``reversed(sl)`` instead')

	def islice(self, start=None, stop=None, reverse=False):
		_len = self._len
		if not _len:
			return iter(())
		(start, stop, _) = slice(start, stop).indices(self._len)
		if start >= stop:
			return iter(())
		_pos = self._pos
		(min_pos, min_idx) = _pos(start)
		if stop == _len:
			max_pos = len(self._lists) - 1
			max_idx = len(self._lists[-1])
		else:
			(max_pos, max_idx) = _pos(stop)
		return self._islice(min_pos, min_idx, max_pos, max_idx, reverse)

	def _islice(self, min_pos, min_idx, max_pos, max_idx, reverse):
		_lists = self._lists
		if min_pos > max_pos:
			return iter(())
		if min_pos == max_pos:
			if reverse:
				indices = reversed(range(min_idx, max_idx))
				return map(_lists[min_pos].__getitem__, indices)
			indices = range(min_idx, max_idx)
			return map(_lists[min_pos].__getitem__, indices)
		next_pos = min_pos + 1
		if next_pos == max_pos:
			if reverse:
				min_indices = range(min_idx, len(_lists[min_pos]))
				max_indices = range(max_idx)
				return chain(map(_lists[max_pos].__getitem__, reversed(max_indices)), map(_lists[min_pos].__getitem__, reversed(min_indices)))
			min_indices = range(min_idx, len(_lists[min_pos]))
			max_indices = range(max_idx)
			return chain(map(_lists[min_pos].__getitem__, min_indices), map(_lists[max_pos].__getitem__, max_indices))
		if reverse:
			min_indices = range(min_idx, len(_lists[min_pos]))
			sublist_indices = range(next_pos, max_pos)
			sublists = map(_lists.__getitem__, reversed(sublist_indices))
			max_indices = range(max_idx)
			return chain(map(_lists[max_pos].__getitem__, reversed(max_indices)), chain.from_iterable(map(reversed, sublists)), map(_lists[min_pos].__getitem__, reversed(min_indices)))
		min_indices = range(min_idx, len(_lists[min_pos]))
		sublist_indices = range(next_pos, max_pos)
		sublists = map(_lists.__getitem__, sublist_indices)
		max_indices = range(max_idx)
		return chain(map(_lists[min_pos].__getitem__, min_indices), chain.from_iterable(sublists), map(_lists[max_pos].__getitem__, max_indices))

	def irange(self, minimum=None, maximum=None, inclusive=(True, True), reverse=False):
		_maxes = self._maxes
		if not _maxes:
			return iter(())
		_lists = self._lists
		if minimum is None:
			min_pos = 0
			min_idx = 0
		elif inclusive[0]:
			min_pos = bisect_left(_maxes, minimum)
			if min_pos == len(_maxes):
				return iter(())
			min_idx = bisect_left(_lists[min_pos], minimum)
		else:
			min_pos = bisect_right(_maxes, minimum)
			if min_pos == len(_maxes):
				return iter(())
			min_idx = bisect_right(_lists[min_pos], minimum)
		if maximum is None:
			max_pos = len(_maxes) - 1
			max_idx = len(_lists[max_pos])
		elif inclusive[1]:
			max_pos = bisect_right(_maxes, maximum)
			if max_pos == len(_maxes):
				max_pos -= 1
				max_idx = len(_lists[max_pos])
			else:
				max_idx = bisect_right(_lists[max_pos], maximum)
		else:
			max_pos = bisect_left(_maxes, maximum)
			if max_pos == len(_maxes):
				max_pos -= 1
				max_idx = len(_lists[max_pos])
			else:
				max_idx = bisect_left(_lists[max_pos], maximum)
		return self._islice(min_pos, min_idx, max_pos, max_idx, reverse)

	def __len__(self):
		return self._len

	def bisect_left(self, value):
		_maxes = self._maxes
		if not _maxes:
			return 0
		pos = bisect_left(_maxes, value)
		if pos == len(_maxes):
			return self._len
		idx = bisect_left(self._lists[pos], value)
		return self._loc(pos, idx)

	def bisect_right(self, value):
		_maxes = self._maxes
		if not _maxes:
			return 0
		pos = bisect_right(_maxes, value)
		if pos == len(_maxes):
			return self._len
		idx = bisect_right(self._lists[pos], value)
		return self._loc(pos, idx)
	bisect = bisect_right
	_bisect_right = bisect_right

	def count(self, value):
		_maxes = self._maxes
		if not _maxes:
			return 0
		pos_left = bisect_left(_maxes, value)
		if pos_left == len(_maxes):
			return 0
		_lists = self._lists
		idx_left = bisect_left(_lists[pos_left], value)
		pos_right = bisect_right(_maxes, value)
		if pos_right == len(_maxes):
			return self._len - self._loc(pos_left, idx_left)
		idx_right = bisect_right(_lists[pos_right], value)
		if pos_left == pos_right:
			return idx_right - idx_left
		right = self._loc(pos_right, idx_right)
		left = self._loc(pos_left, idx_left)
		return right - left

	def copy(self):
		return self.__class__(self)
	__copy__ = copy

	def append(self, value):
		raise NotImplementedError('use ``sl.add(value)`` instead')

	def extend(self, values):
		raise NotImplementedError('use ``sl.update(values)`` instead')

	def insert(self, index, value):
		raise NotImplementedError('use ``sl.add(value)`` instead')

	def pop(self, index=-1):
		if not self._len:
			raise IndexError('pop index out of range')
		_lists = self._lists
		if index == 0:
			val = _lists[0][0]
			self._delete(0, 0)
			return val
		if index == -1:
			pos = len(_lists) - 1
			loc = len(_lists[pos]) - 1
			val = _lists[pos][loc]
			self._delete(pos, loc)
			return val
		if 0 <= index < len(_lists[0]):
			val = _lists[0][index]
			self._delete(0, index)
			return val
		len_last = len(_lists[-1])
		if -len_last < index < 0:
			pos = len(_lists) - 1
			loc = len_last + index
			val = _lists[pos][loc]
			self._delete(pos, loc)
			return val
		(pos, idx) = self._pos(index)
		val = _lists[pos][idx]
		self._delete(pos, idx)
		return val

	def index(self, value, start=None, stop=None):
		_len = self._len
		if not _len:
			raise ValueError('{0!r} is not in list'.format(value))
		if start is None:
			start = 0
		if start < 0:
			start += _len
		if start < 0:
			start = 0
		if stop is None:
			stop = _len
		if stop < 0:
			stop += _len
		if stop > _len:
			stop = _len
		if stop <= start:
			raise ValueError('{0!r} is not in list'.format(value))
		_maxes = self._maxes
		pos_left = bisect_left(_maxes, value)
		if pos_left == len(_maxes):
			raise ValueError('{0!r} is not in list'.format(value))
		_lists = self._lists
		idx_left = bisect_left(_lists[pos_left], value)
		if _lists[pos_left][idx_left] != value:
			raise ValueError('{0!r} is not in list'.format(value))
		stop -= 1
		left = self._loc(pos_left, idx_left)
		if start <= left:
			if left <= stop:
				return left
		else:
			right = self._bisect_right(value) - 1
			if start <= right:
				return start
		raise ValueError('{0!r} is not in list'.format(value))

	def __add__(self, other):
		values = reduce(iadd, self._lists, [])
		values.extend(other)
		return self.__class__(values)
	__radd__ = __add__

	def __iadd__(self, other):
		self._update(other)
		return self

	def __mul__(self, num):
		values = reduce(iadd, self._lists, []) * num
		return self.__class__(values)
	__rmul__ = __mul__

	def __imul__(self, num):
		values = reduce(iadd, self._lists, []) * num
		self._clear()
		self._update(values)
		return self

	def __make_cmp(seq_op, symbol, doc):

		def comparer(self, other):
			if not isinstance(other, Sequence):
				return NotImplemented
			self_len = self._len
			len_other = len(other)
			if self_len != len_other:
				if seq_op is eq:
					return False
				if seq_op is ne:
					return True
			for (alpha, beta) in zip(self, other):
				if alpha != beta:
					return seq_op(alpha, beta)
			return seq_op(self_len, len_other)
		seq_op_name = seq_op.__name__
		comparer.__name__ = '__{0}__'.format(seq_op_name)
		doc_str = 'Return true if and only if sorted list is {0} `other`.\n\n        ``sl.__{1}__(other)`` <==> ``sl {2} other``\n\n        Comparisons use lexicographical order as with sequences.\n\n        Runtime complexity: `O(n)`\n\n        :param other: `other` sequence\n        :return: true if sorted list is {0} `other`\n\n        '
		comparer.__doc__ = dedent(doc_str.format(doc, seq_op_name, symbol))
		return comparer
	__eq__ = __make_cmp(eq, '==', 'equal to')
	__ne__ = __make_cmp(ne, '!=', 'not equal to')
	__lt__ = __make_cmp(lt, '<', 'less than')
	__gt__ = __make_cmp(gt, '>', 'greater than')
	__le__ = __make_cmp(le, '<=', 'less than or equal to')
	__ge__ = __make_cmp(ge, '>=', 'greater than or equal to')
	__make_cmp = staticmethod(__make_cmp)

	def __reduce__(self):
		values = reduce(iadd, self._lists, [])
		return (type(self), (values,))

	@recursive_repr()
	def __repr__(self):
		return '{0}({1!r})'.format(type(self).__name__, list(self))

	def _check(self):
		try:
			assert self._load >= 4
			assert len(self._maxes) == len(self._lists)
			assert self._len == sum((len(sublist) for sublist in self._lists))
			for sublist in self._lists:
				for pos in range(1, len(sublist)):
					assert sublist[pos - 1] <= sublist[pos]
			for pos in range(1, len(self._lists)):
				assert self._lists[pos - 1][-1] <= self._lists[pos][0]
			for pos in range(len(self._maxes)):
				assert self._maxes[pos] == self._lists[pos][-1]
			double = self._load << 1
			assert all((len(sublist) <= double for sublist in self._lists))
			half = self._load >> 1
			for pos in range(0, len(self._lists) - 1):
				assert len(self._lists[pos]) >= half
			if self._index:
				assert self._len == self._index[0]
				assert len(self._index) == self._offset + len(self._lists)
				for pos in range(len(self._lists)):
					leaf = self._index[self._offset + pos]
					assert leaf == len(self._lists[pos])
				for pos in range(self._offset):
					child = (pos << 1) + 1
					if child >= len(self._index):
						assert self._index[pos] == 0
					elif child + 1 == len(self._index):
						assert self._index[pos] == self._index[child]
					else:
						child_sum = self._index[child] + self._index[child + 1]
						assert child_sum == self._index[pos]
		except:
			traceback.print_exc(file=sys.stdout)
			print('len', self._len)
			print('load', self._load)
			print('offset', self._offset)
			print('len_index', len(self._index))
			print('index', self._index)
			print('len_maxes', len(self._maxes))
			print('maxes', self._maxes)
			print('len_lists', len(self._lists))
			print('lists', self._lists)
			raise

def identity(value):
	return value

class SortedKeyList(SortedList):

	def __init__(self, iterable=None, key=identity):
		self._key = key
		self._len = 0
		self._load = self.DEFAULT_LOAD_FACTOR
		self._lists = []
		self._keys = []
		self._maxes = []
		self._index = []
		self._offset = 0
		if iterable is not None:
			self._update(iterable)

	def __new__(cls, iterable=None, key=identity):
		return object.__new__(cls)

	@property
	def key(self):
		return self._key

	def clear(self):
		self._len = 0
		del self._lists[:]
		del self._keys[:]
		del self._maxes[:]
		del self._index[:]
	_clear = clear

	def add(self, value):
		_lists = self._lists
		_keys = self._keys
		_maxes = self._maxes
		key = self._key(value)
		if _maxes:
			pos = bisect_right(_maxes, key)
			if pos == len(_maxes):
				pos -= 1
				_lists[pos].append(value)
				_keys[pos].append(key)
				_maxes[pos] = key
			else:
				idx = bisect_right(_keys[pos], key)
				_lists[pos].insert(idx, value)
				_keys[pos].insert(idx, key)
			self._expand(pos)
		else:
			_lists.append([value])
			_keys.append([key])
			_maxes.append(key)
		self._len += 1

	def _expand(self, pos):
		_lists = self._lists
		_keys = self._keys
		_index = self._index
		if len(_keys[pos]) > self._load << 1:
			_maxes = self._maxes
			_load = self._load
			_lists_pos = _lists[pos]
			_keys_pos = _keys[pos]
			half = _lists_pos[_load:]
			half_keys = _keys_pos[_load:]
			del _lists_pos[_load:]
			del _keys_pos[_load:]
			_maxes[pos] = _keys_pos[-1]
			_lists.insert(pos + 1, half)
			_keys.insert(pos + 1, half_keys)
			_maxes.insert(pos + 1, half_keys[-1])
			del _index[:]
		elif _index:
			child = self._offset + pos
			while child:
				_index[child] += 1
				child = child - 1 >> 1
			_index[0] += 1

	def update(self, iterable):
		_lists = self._lists
		_keys = self._keys
		_maxes = self._maxes
		values = sorted(iterable, key=self._key)
		if _maxes:
			if len(values) * 4 >= self._len:
				values.extend(chain.from_iterable(_lists))
				values.sort(key=self._key)
				self._clear()
			else:
				_add = self.add
				for val in values:
					_add(val)
				return
		_load = self._load
		_lists.extend((values[pos:pos + _load] for pos in range(0, len(values), _load)))
		_keys.extend((list(map(self._key, _list)) for _list in _lists))
		_maxes.extend((sublist[-1] for sublist in _keys))
		self._len = len(values)
		del self._index[:]
	_update = update

	def __contains__(self, value):
		_maxes = self._maxes
		if not _maxes:
			return False
		key = self._key(value)
		pos = bisect_left(_maxes, key)
		if pos == len(_maxes):
			return False
		_lists = self._lists
		_keys = self._keys
		idx = bisect_left(_keys[pos], key)
		len_keys = len(_keys)
		len_sublist = len(_keys[pos])
		while True:
			if _keys[pos][idx] != key:
				return False
			if _lists[pos][idx] == value:
				return True
			idx += 1
			if idx == len_sublist:
				pos += 1
				if pos == len_keys:
					return False
				len_sublist = len(_keys[pos])
				idx = 0

	def discard(self, value):
		_maxes = self._maxes
		if not _maxes:
			return
		key = self._key(value)
		pos = bisect_left(_maxes, key)
		if pos == len(_maxes):
			return
		_lists = self._lists
		_keys = self._keys
		idx = bisect_left(_keys[pos], key)
		len_keys = len(_keys)
		len_sublist = len(_keys[pos])
		while True:
			if _keys[pos][idx] != key:
				return
			if _lists[pos][idx] == value:
				self._delete(pos, idx)
				return
			idx += 1
			if idx == len_sublist:
				pos += 1
				if pos == len_keys:
					return
				len_sublist = len(_keys[pos])
				idx = 0

	def remove(self, value):
		_maxes = self._maxes
		if not _maxes:
			raise ValueError('{0!r} not in list'.format(value))
		key = self._key(value)
		pos = bisect_left(_maxes, key)
		if pos == len(_maxes):
			raise ValueError('{0!r} not in list'.format(value))
		_lists = self._lists
		_keys = self._keys
		idx = bisect_left(_keys[pos], key)
		len_keys = len(_keys)
		len_sublist = len(_keys[pos])
		while True:
			if _keys[pos][idx] != key:
				raise ValueError('{0!r} not in list'.format(value))
			if _lists[pos][idx] == value:
				self._delete(pos, idx)
				return
			idx += 1
			if idx == len_sublist:
				pos += 1
				if pos == len_keys:
					raise ValueError('{0!r} not in list'.format(value))
				len_sublist = len(_keys[pos])
				idx = 0

	def _delete(self, pos, idx):
		_lists = self._lists
		_keys = self._keys
		_maxes = self._maxes
		_index = self._index
		keys_pos = _keys[pos]
		lists_pos = _lists[pos]
		del keys_pos[idx]
		del lists_pos[idx]
		self._len -= 1
		len_keys_pos = len(keys_pos)
		if len_keys_pos > self._load >> 1:
			_maxes[pos] = keys_pos[-1]
			if _index:
				child = self._offset + pos
				while child > 0:
					_index[child] -= 1
					child = child - 1 >> 1
				_index[0] -= 1
		elif len(_keys) > 1:
			if not pos:
				pos += 1
			prev = pos - 1
			_keys[prev].extend(_keys[pos])
			_lists[prev].extend(_lists[pos])
			_maxes[prev] = _keys[prev][-1]
			del _lists[pos]
			del _keys[pos]
			del _maxes[pos]
			del _index[:]
			self._expand(prev)
		elif len_keys_pos:
			_maxes[pos] = keys_pos[-1]
		else:
			del _lists[pos]
			del _keys[pos]
			del _maxes[pos]
			del _index[:]

	def irange(self, minimum=None, maximum=None, inclusive=(True, True), reverse=False):
		min_key = self._key(minimum) if minimum is not None else None
		max_key = self._key(maximum) if maximum is not None else None
		return self._irange_key(min_key=min_key, max_key=max_key, inclusive=inclusive, reverse=reverse)

	def irange_key(self, min_key=None, max_key=None, inclusive=(True, True), reverse=False):
		_maxes = self._maxes
		if not _maxes:
			return iter(())
		_keys = self._keys
		if min_key is None:
			min_pos = 0
			min_idx = 0
		elif inclusive[0]:
			min_pos = bisect_left(_maxes, min_key)
			if min_pos == len(_maxes):
				return iter(())
			min_idx = bisect_left(_keys[min_pos], min_key)
		else:
			min_pos = bisect_right(_maxes, min_key)
			if min_pos == len(_maxes):
				return iter(())
			min_idx = bisect_right(_keys[min_pos], min_key)
		if max_key is None:
			max_pos = len(_maxes) - 1
			max_idx = len(_keys[max_pos])
		elif inclusive[1]:
			max_pos = bisect_right(_maxes, max_key)
			if max_pos == len(_maxes):
				max_pos -= 1
				max_idx = len(_keys[max_pos])
			else:
				max_idx = bisect_right(_keys[max_pos], max_key)
		else:
			max_pos = bisect_left(_maxes, max_key)
			if max_pos == len(_maxes):
				max_pos -= 1
				max_idx = len(_keys[max_pos])
			else:
				max_idx = bisect_left(_keys[max_pos], max_key)
		return self._islice(min_pos, min_idx, max_pos, max_idx, reverse)
	_irange_key = irange_key

	def bisect_left(self, value):
		return self._bisect_key_left(self._key(value))

	def bisect_right(self, value):
		return self._bisect_key_right(self._key(value))
	bisect = bisect_right

	def bisect_key_left(self, key):
		_maxes = self._maxes
		if not _maxes:
			return 0
		pos = bisect_left(_maxes, key)
		if pos == len(_maxes):
			return self._len
		idx = bisect_left(self._keys[pos], key)
		return self._loc(pos, idx)
	_bisect_key_left = bisect_key_left

	def bisect_key_right(self, key):
		_maxes = self._maxes
		if not _maxes:
			return 0
		pos = bisect_right(_maxes, key)
		if pos == len(_maxes):
			return self._len
		idx = bisect_right(self._keys[pos], key)
		return self._loc(pos, idx)
	bisect_key = bisect_key_right
	_bisect_key_right = bisect_key_right

	def count(self, value):
		_maxes = self._maxes
		if not _maxes:
			return 0
		key = self._key(value)
		pos = bisect_left(_maxes, key)
		if pos == len(_maxes):
			return 0
		_lists = self._lists
		_keys = self._keys
		idx = bisect_left(_keys[pos], key)
		total = 0
		len_keys = len(_keys)
		len_sublist = len(_keys[pos])
		while True:
			if _keys[pos][idx] != key:
				return total
			if _lists[pos][idx] == value:
				total += 1
			idx += 1
			if idx == len_sublist:
				pos += 1
				if pos == len_keys:
					return total
				len_sublist = len(_keys[pos])
				idx = 0

	def copy(self):
		return self.__class__(self, key=self._key)
	__copy__ = copy

	def index(self, value, start=None, stop=None):
		_len = self._len
		if not _len:
			raise ValueError('{0!r} is not in list'.format(value))
		if start is None:
			start = 0
		if start < 0:
			start += _len
		if start < 0:
			start = 0
		if stop is None:
			stop = _len
		if stop < 0:
			stop += _len
		if stop > _len:
			stop = _len
		if stop <= start:
			raise ValueError('{0!r} is not in list'.format(value))
		_maxes = self._maxes
		key = self._key(value)
		pos = bisect_left(_maxes, key)
		if pos == len(_maxes):
			raise ValueError('{0!r} is not in list'.format(value))
		stop -= 1
		_lists = self._lists
		_keys = self._keys
		idx = bisect_left(_keys[pos], key)
		len_keys = len(_keys)
		len_sublist = len(_keys[pos])
		while True:
			if _keys[pos][idx] != key:
				raise ValueError('{0!r} is not in list'.format(value))
			if _lists[pos][idx] == value:
				loc = self._loc(pos, idx)
				if start <= loc <= stop:
					return loc
				elif loc > stop:
					break
			idx += 1
			if idx == len_sublist:
				pos += 1
				if pos == len_keys:
					raise ValueError('{0!r} is not in list'.format(value))
				len_sublist = len(_keys[pos])
				idx = 0
		raise ValueError('{0!r} is not in list'.format(value))

	def __add__(self, other):
		values = reduce(iadd, self._lists, [])
		values.extend(other)
		return self.__class__(values, key=self._key)
	__radd__ = __add__

	def __mul__(self, num):
		values = reduce(iadd, self._lists, []) * num
		return self.__class__(values, key=self._key)

	def __reduce__(self):
		values = reduce(iadd, self._lists, [])
		return (type(self), (values, self.key))

	@recursive_repr()
	def __repr__(self):
		type_name = type(self).__name__
		return '{0}({1!r}, key={2!r})'.format(type_name, list(self), self._key)

	def _check(self):
		try:
			assert self._load >= 4
			assert len(self._maxes) == len(self._lists) == len(self._keys)
			assert self._len == sum((len(sublist) for sublist in self._lists))
			for sublist in self._keys:
				for pos in range(1, len(sublist)):
					assert sublist[pos - 1] <= sublist[pos]
			for pos in range(1, len(self._keys)):
				assert self._keys[pos - 1][-1] <= self._keys[pos][0]
			for (val_sublist, key_sublist) in zip(self._lists, self._keys):
				assert len(val_sublist) == len(key_sublist)
				for (val, key) in zip(val_sublist, key_sublist):
					assert self._key(val) == key
			for pos in range(len(self._maxes)):
				assert self._maxes[pos] == self._keys[pos][-1]
			double = self._load << 1
			assert all((len(sublist) <= double for sublist in self._lists))
			half = self._load >> 1
			for pos in range(0, len(self._lists) - 1):
				assert len(self._lists[pos]) >= half
			if self._index:
				assert self._len == self._index[0]
				assert len(self._index) == self._offset + len(self._lists)
				for pos in range(len(self._lists)):
					leaf = self._index[self._offset + pos]
					assert leaf == len(self._lists[pos])
				for pos in range(self._offset):
					child = (pos << 1) + 1
					if child >= len(self._index):
						assert self._index[pos] == 0
					elif child + 1 == len(self._index):
						assert self._index[pos] == self._index[child]
					else:
						child_sum = self._index[child] + self._index[child + 1]
						assert child_sum == self._index[pos]
		except:
			traceback.print_exc(file=sys.stdout)
			print('len', self._len)
			print('load', self._load)
			print('offset', self._offset)
			print('len_index', len(self._index))
			print('index', self._index)
			print('len_maxes', len(self._maxes))
			print('maxes', self._maxes)
			print('len_keys', len(self._keys))
			print('keys', self._keys)
			print('len_lists', len(self._lists))
			print('lists', self._lists)
			raise
SortedListWithKey = SortedKeyList
from bisect import *
from collections import *
from math import gcd, ceil, sqrt, floor, inf
from heapq import *
from itertools import *
from operator import add, mul, sub, xor, truediv, floordiv
from functools import *
import os
import sys
from io import BytesIO, IOBase
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')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')

def RL():
	return map(int, sys.stdin.readline().rstrip().split())

def RLL():
	return list(map(int, sys.stdin.readline().rstrip().split()))

def N():
	return int(input())
farr = [1]
ifa = []

def fact(x, mod=0):
	if mod:
		while x >= len(farr):
			farr.append(farr[-1] * len(farr) % mod)
	else:
		while x >= len(farr):
			farr.append(farr[-1] * len(farr))
	return farr[x]

def ifact(x, mod):
	global ifa
	ifa.append(pow(farr[-1], mod - 2, mod))
	for i in range(x, 0, -1):
		ifa.append(ifa[-1] * i % mod)
	ifa = ifa[::-1]

def per(i, j, mod=0):
	if i < j:
		return 0
	if not mod:
		return fact(i) // fact(i - j)
	return farr[i] * ifa[i - j] % mod

def com(i, j, mod=0):
	if i < j:
		return 0
	if not mod:
		return per(i, j) // fact(j)
	return per(i, j, mod) * ifa[j] % mod

def catalan(n):
	return com(2 * n, n) // (n + 1)

def linc(f, t, l, r):
	while l < r:
		mid = (l + r) // 2
		if t > f(mid):
			l = mid + 1
		else:
			r = mid
	return l

def rinc(f, t, l, r):
	while l < r:
		mid = (l + r + 1) // 2
		if t < f(mid):
			r = mid - 1
		else:
			l = mid
	return l

def ldec(f, t, l, r):
	while l < r:
		mid = (l + r) // 2
		if t < f(mid):
			l = mid + 1
		else:
			r = mid
	return l

def rdec(f, t, l, r):
	while l < r:
		mid = (l + r + 1) // 2
		if t > f(mid):
			r = mid - 1
		else:
			l = mid
	return l

def isprime(n):
	for i in range(2, int(n ** 0.5) + 1):
		if n % i == 0:
			return False
	return True

def binfun(x):
	c = 0
	for w in arr:
		c += ceil(w / x)
	return c

def lowbit(n):
	return n & -n

def inverse(a, m):
	a %= m
	if a <= 1:
		return a
	return (1 - inverse(m, a) * m) // a % m

class BIT:

	def __init__(self, arr):
		self.arr = arr
		self.n = len(arr) - 1

	def update(self, x, v):
		while x <= self.n:
			self.arr[x] += v
			x += x & -x

	def query(self, x):
		ans = 0
		while x:
			ans += self.arr[x]
			x &= x - 1
		return ans

class smt:

	def __init__(self, l, r, arr):
		self.l = l
		self.r = r
		self.value = (1 << 31) - 1 if l < r else arr[l]
		mid = (l + r) // 2
		if l < r:
			self.left = smt(l, mid, arr)
			self.right = smt(mid + 1, r, arr)
			self.value &= self.left.value & self.right.value

	def setvalue(self, x, val):
		if self.l == self.r:
			self.value = val
			return
		mid = (self.l + self.r) // 2
		if x <= mid:
			self.left.setvalue(x, val)
		else:
			self.right.setvalue(x, val)
		self.value = self.left.value & self.right.value

	def ask(self, l, r):
		if l <= self.l and r >= self.r:
			return self.value
		val = (1 << 31) - 1
		mid = (self.l + self.r) // 2
		if l <= mid:
			val &= self.left.ask(l, r)
		if r > mid:
			val &= self.right.ask(l, r)
		return val

class DSU:

	def __init__(self, n):
		self.c = [-1] * n

	def same(self, x, y):
		return self.find(x) == self.find(y)

	def find(self, x):
		if self.c[x] < 0:
			return x
		self.c[x] = self.find(self.c[x])
		return self.c[x]

	def union(self, u, v):
		(u, v) = (self.find(u), self.find(v))
		if u == v:
			return False
		if self.c[u] < self.c[v]:
			(u, v) = (v, u)
		self.c[u] += self.c[v]
		self.c[v] = u
		return True

	def size(self, x):
		return -self.c[self.find(x)]

class UFS:

	def __init__(self, n):
		self.parent = [i for i in range(n)]
		self.ranks = [0] * n

	def find(self, x):
		if x != self.parent[x]:
			self.parent[x] = self.find(self.parent[x])
		return self.parent[x]

	def union(self, u, v):
		(pu, pv) = (self.find(u), self.find(v))
		if pu == pv:
			return False
		if self.ranks[pu] >= self.ranks[pv]:
			self.parent[pv] = pu
			if self.ranks[pv] == self.ranks[pu]:
				self.ranks[pu] += 1
		else:
			self.parent[pu] = pv

def Prime(n):
	c = 0
	prime = []
	flag = [0] * (n + 1)
	for i in range(2, n + 1):
		if not flag[i]:
			prime.append(i)
			c += 1
		for j in range(c):
			if i * prime[j] > n:
				break
			flag[i * prime[j]] = prime[j]
			if i % prime[j] == 0:
				break
	return prime

def dij(s, graph):
	d = {}
	d[s] = 0
	heap = [(0, s)]
	seen = set()
	while heap:
		(dis, u) = heappop(heap)
		if u in seen:
			continue
		for v in graph[u]:
			if v not in d or d[v] > d[u] + graph[u][v]:
				d[v] = d[u] + graph[u][v]
				heappush(heap, (d[v], v))
	return d

def GP(it):
	return [(ch, len(list(g))) for (ch, g) in groupby(it)]

class DLN:

	def __init__(self, val):
		self.val = val
		self.pre = None
		self.next = None
t = 1
for i in range(t):
	(n, q) = RL()
	p = RLL()
	p.sort()
	s = SortedList(p)
	s2 = SortedList([p[i] - p[i - 1] for i in range(1, n)])
	ans = 0 if len(s) < 3 else s[-1] - s[0] - s2[-1]
	print(ans)
	for i in range(q):
		(t, x) = RL()
		if t == 0:
			ind = s.index(x)
			if ind == 0:
				if len(s) > 1:
					r = s[1] - s[0]
					s2.remove(r)
			elif ind == len(s) - 1:
				r = s[ind] - s[ind - 1]
				s2.remove(r)
			else:
				r1 = s[ind] - s[ind - 1]
				r2 = s[ind + 1] - s[ind]
				s2.remove(r1)
				s2.remove(r2)
				s2.add(r1 + r2)
			s.remove(x)
			ans = 0 if len(s) < 3 else s[-1] - s[0] - s2[-1]
			print(ans)
		else:
			ind = s.bisect(x)
			if ind == len(s):
				if ind != 0:
					r = x - s[-1]
					s2.add(r)
			elif ind == 0:
				r = s[0] - x
				s2.add(r)
			else:
				r1 = x - s[ind - 1]
				r2 = s[ind] - x
				s2.remove(r1 + r2)
				s2.add(r1)
				s2.add(r2)
			s.add(x)
			ans = 0 if len(s) < 3 else s[-1] - s[0] - s2[-1]
			print(ans)


import io
import os
from collections import Counter, defaultdict, deque

class SegmentTree:

	def __init__(self, data, default=0, func=max):
		self._default = default
		self._func = func
		self._len = len(data)
		self._size = _size = 1 << (self._len - 1).bit_length()
		self.data = [default] * (2 * _size)
		self.data[_size:_size + self._len] = data
		for i in reversed(range(_size)):
			self.data[i] = func(self.data[i + i], self.data[i + i + 1])

	def __delitem__(self, idx):
		self[idx] = self._default

	def __getitem__(self, idx):
		return self.data[idx + self._size]

	def __setitem__(self, idx, value):
		idx += self._size
		self.data[idx] = value
		idx >>= 1
		while idx:
			self.data[idx] = self._func(self.data[2 * idx], self.data[2 * idx + 1])
			idx >>= 1

	def __len__(self):
		return self._len

	def query(self, start, stop):
		start += self._size
		stop += self._size
		res_left = res_right = self._default
		while start < stop:
			if start & 1:
				res_left = self._func(res_left, self.data[start])
				start += 1
			if stop & 1:
				stop -= 1
				res_right = self._func(self.data[stop], res_right)
			start >>= 1
			stop >>= 1
		return self._func(res_left, res_right)

	def __repr__(self):
		return 'SegmentTree({0})'.format(self.data)

class Node:

	def __init__(self, count, mn, mx, maxGap):
		self.count = count
		self.mn = mn
		self.mx = mx
		self.maxGap = maxGap
neutral = Node(0, 0, 0, 0)

def combine(x, y):
	if x.count == 0:
		return y
	if y.count == 0:
		return x
	return Node(x.count + y.count, min(x.mn, y.mn), max(y.mx, y.mx), max(y.mn - x.mx, x.maxGap, y.maxGap))

def solve(N, Q, P, TX):
	allPoints = sorted(set(P + [x for (t, x) in TX]))
	compress = {}
	for (i, x) in enumerate(allPoints):
		compress[x] = i
	counts = [0] * len(allPoints)
	segTree = SegmentTree([neutral] * len(allPoints), neutral, combine)
	for x in P:
		index = compress[x]
		counts[index] += 1
		segTree[index] = Node(counts[index], x, x, 0)

	def query():
		node = segTree.query(0, len(allPoints))
		if node.count == 1:
			return 0
		return node.mx - node.mn - node.maxGap
	ans = [query()]
	for (t, x) in TX:
		index = compress[x]
		if t == 0:
			counts[index] -= 1
		else:
			counts[index] += 1
			assert t == 1
		segTree[index] = Node(counts[index], x, x, 0)
		ans.append(query())
	return '\n'.join(map(str, ans))
input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline
(N, Q) = [int(x) for x in input().split()]
P = [int(x) for x in input().split()]
TX = [[int(x) for x in input().split()] for i in range(Q)]
ans = solve(N, Q, P, TX)
print(ans)


import io, os
input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline

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))
(n, q) = map(int, input().split())
arr = list(map(int, input().split()))
arr = sorted(arr)
d = [0]
for i in range(n - 1):
	d.append(arr[i + 1] - arr[i])
sorted_arr = Sortedlist(arr)
sorted_d = Sortedlist(d)
print(sorted_arr[-1] - sorted_arr[0] - sorted_d[-1])
for j in range(q):
	(op, x) = map(int, input().split())
	if op == 0:
		loc = sorted_arr.bisect_left(x)
		(frontd, reard) = (0, 0)
		if 0 < loc < len(sorted_arr):
			frontd = sorted_arr[loc] - sorted_arr[loc - 1]
		if loc < len(sorted_arr) - 1:
			reard = sorted_arr[loc + 1] - sorted_arr[loc]
		sorted_arr.pop(loc)
		if frontd > 0:
			loc1 = sorted_d.bisect_left(frontd)
			sorted_d.pop(loc1)
		if reard > 0:
			loc2 = sorted_d.bisect_left(reard)
			sorted_d.pop(loc2)
		if frontd > 0 and reard > 0:
			sorted_d.add(frontd + reard)
	else:
		loc = sorted_arr.bisect_left(x)
		(frontd, reard) = (0, 0)
		if loc > 0:
			frontd = x - sorted_arr[loc - 1]
		if loc < len(sorted_arr):
			reard = sorted_arr[loc] - x
		sorted_arr.add(x)
		if frontd > 0:
			sorted_d.add(frontd)
		if reard > 0:
			sorted_d.add(reard)
		if frontd > 0 and reard > 0:
			loct = sorted_d.bisect_left(frontd + reard)
			sorted_d.pop(loct)
	if len(sorted_arr) > 0 and len(sorted_d) > 0:
		print(sorted_arr[-1] - sorted_arr[0] - sorted_d[-1])
	else:
		print(0)


from __future__ import division, print_function
from fractions import Fraction
import sys
import os
from io import BytesIO, IOBase
from itertools import *
import bisect
from heapq import *
from math import ceil, floor
from copy import *
from collections import deque, defaultdict
from collections import Counter as counter
from itertools import combinations
from itertools import permutations as permutate
from bisect import bisect_left as bl
from operator import *
from bisect import bisect_right as br
from bisect import bisect
BUFSIZE = 8192
from sys import stderr

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')

def print(*args, **kwargs):
	(sep, file) = (kwargs.pop('sep', ' '), kwargs.pop('file', sys.stdout))
	at_start = True
	for x in args:
		if not at_start:
			file.write(sep)
		file.write(str(x))
		at_start = False
	file.write(kwargs.pop('end', '\n'))
	if kwargs.pop('flush', False):
		file.flush()
if sys.version_info[0] < 3:
	(sys.stdin, sys.stdout) = (FastIO(sys.stdin), FastIO(sys.stdout))
else:
	(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
from types import GeneratorType

def iterative(f, stack=[]):

	def wrapped_func(*args, **kwargs):
		if stack:
			return f(*args, **kwargs)
		to = f(*args, **kwargs)
		while True:
			if type(to) is GeneratorType:
				stack.append(to)
				to = next(to)
				continue
			stack.pop()
			if not stack:
				break
			to = stack[-1].send(to)
		return to
	return wrapped_func
mod = 1000000007

def inp():
	return sys.stdin.readline().rstrip('\r\n')

def out(var):
	sys.stdout.write(str(var))

def lis():
	return list(map(int, inp().split()))

def stringlis():
	return list(map(str, inp().split()))

def sep():
	return map(int, inp().split())

def strsep():
	return map(str, inp().split())

def fsep():
	return map(float, inp().split())

def nextline():
	out('\n')

def testcase(t):
	for p in range(t):
		solve()

def pow(x, y, p):
	res = 1
	x = x % p
	if x == 0:
		return 0
	while y > 0:
		if y & 1 == 1:
			res = res * x % p
		y = y >> 1
		x = x * x % p
	return res
from functools import reduce

def factors(n):
	return set(reduce(list.__add__, ([i, n // i] for i in range(1, int(n ** 0.5) + 1) if n % i == 0)))

def gcd(a, b):
	if a == b:
		return a
	while b > 0:
		(a, b) = (b, a % b)
	return a

def comb(n, r):
	if n < r:
		return 0
	else:
		return fac[n] * (finv[r] * finv[n - r] % mod) % mod

def prefix_sum(ar):
	return list(accumulate(ar))

def suffix_sum(ar):
	return list(accumulate(ar[::-1]))[::-1]

def N():
	return int(inp())
from collections import defaultdict
sys.setrecursionlimit(300000)

def numberOfSetBits(i):
	i = i - (i >> 1 & 1431655765)
	i = (i & 858993459) + (i >> 2 & 858993459)
	return ((i + (i >> 4) & 252645135) * 16843009 & 4294967295) >> 24
from math import factorial

def solve():

	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))

	def ans(sl, gap):
		if len(sl) < 3:
			print(0)
			return
		print(sl[len(sl) - 1] - sl[0] - gap[len(gap) - 1])
	if 1:
		(n, q) = sep()
		a = lis()
		sl = SortedList(a)
		gep = []
		for i in range(1, len(sl)):
			gep.append(sl[i] - sl[i - 1])
		gap = SortedList(gep)
		ans(sl, gap)
		for ii in range(q):
			(x, y) = sep()
			if x == 1:
				ind = bl(sl, y)
				if len(sl) > 0:
					if ind == len(sl):
						gap.add(y - sl[ind - 1])
					elif ind == 0:
						gap.add(sl[ind] - y)
					else:
						gap.remove(sl[ind] - sl[ind - 1])
						gap.add(sl[ind] - y)
						gap.add(y - sl[ind - 1])
				sl.add(y)
				ans(sl, gap)
			else:
				ind = bl(sl, y)
				if ind != len(sl) - 1:
					gap.remove(sl[ind + 1] - sl[ind])
				if ind > 0:
					gap.remove(sl[ind] - sl[ind - 1])
				if ind < len(sl) - 1 and ind > 0:
					gap.add(sl[ind + 1] - sl[ind - 1])
				sl.remove(y)
				ans(sl, gap)
solve()


import sys, math
import io, os
from bisect import bisect_left as bl, bisect_right as br, insort
from heapq import heapify, heappush, heappop
from collections import defaultdict as dd, deque, Counter

def data():
	return sys.stdin.readline().strip()

def mdata():
	return list(map(int, data().split()))

def outl(var):
	sys.stdout.write(' '.join(map(str, var)) + '\n')

def out(var):
	sys.stdout.write(str(var) + '\n')
from decimal import Decimal
mod = int(1000000000.0) + 7
INF = float('inf')

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))

def Add(x):
	P.add(x)
	k = P.bisect_left(x)
	if k > 0:
		diff.add(P[k] - P[k - 1])
	if k < len(P) - 1:
		diff.add(P[k + 1] - P[k])
	if 0 < k < len(P) - 1:
		diff.remove(P[k + 1] - P[k - 1])

def Remove(x):
	k = P.bisect_left(x)
	if k > 0:
		diff.remove(P[k] - P[k - 1])
	if k < len(P) - 1:
		diff.remove(P[k + 1] - P[k])
	if 0 < k < len(P) - 1:
		diff.add(P[k + 1] - P[k - 1])
	P.remove(x)
(n, q) = mdata()
P = SortedList(mdata())
diff = SortedList()
for i in range(n - 1):
	diff.add(P[i + 1] - P[i])
if len(P) < 2:
	out(0)
else:
	out(P[-1] - P[0] - diff[-1])
for i in range(q):
	(t, x) = mdata()
	if t == 1:
		Add(x)
	else:
		Remove(x)
	if len(P) < 2:
		out(0)
	else:
		out(P[-1] - P[0] - diff[-1])


import sys
import traceback
from bisect import bisect_left, bisect_right, insort
from itertools import chain, repeat, starmap
from math import log
from operator import add, eq, ne, gt, ge, lt, le, iadd
from textwrap import dedent
try:
	from collections.abc import Sequence, MutableSequence
except ImportError:
	from collections import Sequence, MutableSequence
from functools import wraps
from sys import hexversion
if hexversion < 50331648:
	try:
		from _thread import get_ident
	except ImportError:
		from _dummy_thread import get_ident
else:
	from functools import reduce
	try:
		from _thread import get_ident
	except ImportError:
		from _dummy_thread import get_ident

def recursive_repr(fillvalue='...'):

	def decorating_function(user_function):
		repr_running = set()

		@wraps(user_function)
		def wrapper(self):
			key = (id(self), get_ident())
			if key in repr_running:
				return fillvalue
			repr_running.add(key)
			try:
				result = user_function(self)
			finally:
				repr_running.discard(key)
			return result
		return wrapper
	return decorating_function

class SortedList(MutableSequence):
	DEFAULT_LOAD_FACTOR = 1000

	def __init__(self, iterable=None, key=None):
		assert key is None
		self._len = 0
		self._load = self.DEFAULT_LOAD_FACTOR
		self._lists = []
		self._maxes = []
		self._index = []
		self._offset = 0
		if iterable is not None:
			self._update(iterable)

	def __new__(cls, iterable=None, key=None):
		if key is None:
			return object.__new__(cls)
		elif cls is SortedList:
			return object.__new__(SortedKeyList)
		else:
			raise TypeError('inherit SortedKeyList for key argument')

	@property
	def key(self):
		return None

	def _reset(self, load):
		values = reduce(iadd, self._lists, [])
		self._clear()
		self._load = load
		self._update(values)

	def clear(self):
		self._len = 0
		del self._lists[:]
		del self._maxes[:]
		del self._index[:]
		self._offset = 0
	_clear = clear

	def add(self, value):
		_lists = self._lists
		_maxes = self._maxes
		if _maxes:
			pos = bisect_right(_maxes, value)
			if pos == len(_maxes):
				pos -= 1
				_lists[pos].append(value)
				_maxes[pos] = value
			else:
				insort(_lists[pos], value)
			self._expand(pos)
		else:
			_lists.append([value])
			_maxes.append(value)
		self._len += 1

	def _expand(self, pos):
		_load = self._load
		_lists = self._lists
		_index = self._index
		if len(_lists[pos]) > _load << 1:
			_maxes = self._maxes
			_lists_pos = _lists[pos]
			half = _lists_pos[_load:]
			del _lists_pos[_load:]
			_maxes[pos] = _lists_pos[-1]
			_lists.insert(pos + 1, half)
			_maxes.insert(pos + 1, half[-1])
			del _index[:]
		elif _index:
			child = self._offset + pos
			while child:
				_index[child] += 1
				child = child - 1 >> 1
			_index[0] += 1

	def update(self, iterable):
		_lists = self._lists
		_maxes = self._maxes
		values = sorted(iterable)
		if _maxes:
			if len(values) * 4 >= self._len:
				values.extend(chain.from_iterable(_lists))
				values.sort()
				self._clear()
			else:
				_add = self.add
				for val in values:
					_add(val)
				return
		_load = self._load
		_lists.extend((values[pos:pos + _load] for pos in range(0, len(values), _load)))
		_maxes.extend((sublist[-1] for sublist in _lists))
		self._len = len(values)
		del self._index[:]
	_update = update

	def __contains__(self, value):
		_maxes = self._maxes
		if not _maxes:
			return False
		pos = bisect_left(_maxes, value)
		if pos == len(_maxes):
			return False
		_lists = self._lists
		idx = bisect_left(_lists[pos], value)
		return _lists[pos][idx] == value

	def discard(self, value):
		_maxes = self._maxes
		if not _maxes:
			return
		pos = bisect_left(_maxes, value)
		if pos == len(_maxes):
			return
		_lists = self._lists
		idx = bisect_left(_lists[pos], value)
		if _lists[pos][idx] == value:
			self._delete(pos, idx)

	def remove(self, value):
		_maxes = self._maxes
		if not _maxes:
			raise ValueError('{0!r} not in list'.format(value))
		pos = bisect_left(_maxes, value)
		if pos == len(_maxes):
			raise ValueError('{0!r} not in list'.format(value))
		_lists = self._lists
		idx = bisect_left(_lists[pos], value)
		if _lists[pos][idx] == value:
			self._delete(pos, idx)
		else:
			raise ValueError('{0!r} not in list'.format(value))

	def _delete(self, pos, idx):
		_lists = self._lists
		_maxes = self._maxes
		_index = self._index
		_lists_pos = _lists[pos]
		del _lists_pos[idx]
		self._len -= 1
		len_lists_pos = len(_lists_pos)
		if len_lists_pos > self._load >> 1:
			_maxes[pos] = _lists_pos[-1]
			if _index:
				child = self._offset + pos
				while child > 0:
					_index[child] -= 1
					child = child - 1 >> 1
				_index[0] -= 1
		elif len(_lists) > 1:
			if not pos:
				pos += 1
			prev = pos - 1
			_lists[prev].extend(_lists[pos])
			_maxes[prev] = _lists[prev][-1]
			del _lists[pos]
			del _maxes[pos]
			del _index[:]
			self._expand(prev)
		elif len_lists_pos:
			_maxes[pos] = _lists_pos[-1]
		else:
			del _lists[pos]
			del _maxes[pos]
			del _index[:]

	def _loc(self, pos, idx):
		if not pos:
			return idx
		_index = self._index
		if not _index:
			self._build_index()
		total = 0
		pos += self._offset
		while pos:
			if not pos & 1:
				total += _index[pos - 1]
			pos = pos - 1 >> 1
		return total + idx

	def _pos(self, idx):
		if idx < 0:
			last_len = len(self._lists[-1])
			if -idx <= last_len:
				return (len(self._lists) - 1, last_len + idx)
			idx += self._len
			if idx < 0:
				raise IndexError('list index out of range')
		elif idx >= self._len:
			raise IndexError('list index out of range')
		if idx < len(self._lists[0]):
			return (0, idx)
		_index = self._index
		if not _index:
			self._build_index()
		pos = 0
		child = 1
		len_index = len(_index)
		while child < len_index:
			index_child = _index[child]
			if idx < index_child:
				pos = child
			else:
				idx -= index_child
				pos = child + 1
			child = (pos << 1) + 1
		return (pos - self._offset, idx)

	def _build_index(self):
		row0 = list(map(len, self._lists))
		if len(row0) == 1:
			self._index[:] = row0
			self._offset = 0
			return
		head = iter(row0)
		tail = iter(head)
		row1 = list(starmap(add, list(zip(head, tail))))
		if len(row0) & 1:
			row1.append(row0[-1])
		if len(row1) == 1:
			self._index[:] = row1 + row0
			self._offset = 1
			return
		size = 2 ** (int(log(len(row1) - 1, 2)) + 1)
		row1.extend(repeat(0, size - len(row1)))
		tree = [row0, row1]
		while len(tree[-1]) > 1:
			head = iter(tree[-1])
			tail = iter(head)
			row = list(starmap(add, list(zip(head, tail))))
			tree.append(row)
		reduce(iadd, reversed(tree), self._index)
		self._offset = size * 2 - 1

	def __delitem__(self, index):
		if isinstance(index, slice):
			(start, stop, step) = index.indices(self._len)
			if step == 1 and start < stop:
				if start == 0 and stop == self._len:
					return self._clear()
				elif self._len <= 8 * (stop - start):
					values = self._getitem(slice(None, start))
					if stop < self._len:
						values += self._getitem(slice(stop, None))
					self._clear()
					return self._update(values)
			indices = list(range(start, stop, step))
			if step > 0:
				indices = reversed(indices)
			(_pos, _delete) = (self._pos, self._delete)
			for index in indices:
				(pos, idx) = _pos(index)
				_delete(pos, idx)
		else:
			(pos, idx) = self._pos(index)
			self._delete(pos, idx)

	def __getitem__(self, index):
		_lists = self._lists
		if isinstance(index, slice):
			(start, stop, step) = index.indices(self._len)
			if step == 1 and start < stop:
				if start == 0 and stop == self._len:
					return reduce(iadd, self._lists, [])
				(start_pos, start_idx) = self._pos(start)
				start_list = _lists[start_pos]
				stop_idx = start_idx + stop - start
				if len(start_list) >= stop_idx:
					return start_list[start_idx:stop_idx]
				if stop == self._len:
					stop_pos = len(_lists) - 1
					stop_idx = len(_lists[stop_pos])
				else:
					(stop_pos, stop_idx) = self._pos(stop)
				prefix = _lists[start_pos][start_idx:]
				middle = _lists[start_pos + 1:stop_pos]
				result = reduce(iadd, middle, prefix)
				result += _lists[stop_pos][:stop_idx]
				return result
			if step == -1 and start > stop:
				result = self._getitem(slice(stop + 1, start + 1))
				result.reverse()
				return result
			indices = list(range(start, stop, step))
			return list((self._getitem(index) for index in indices))
		else:
			if self._len:
				if index == 0:
					return _lists[0][0]
				elif index == -1:
					return _lists[-1][-1]
			else:
				raise IndexError('list index out of range')
			if 0 <= index < len(_lists[0]):
				return _lists[0][index]
			len_last = len(_lists[-1])
			if -len_last < index < 0:
				return _lists[-1][len_last + index]
			(pos, idx) = self._pos(index)
			return _lists[pos][idx]
	_getitem = __getitem__

	def __setitem__(self, index, value):
		message = 'use ``del sl[index]`` and ``sl.add(value)`` instead'
		raise NotImplementedError(message)

	def __iter__(self):
		return chain.from_iterable(self._lists)

	def __reversed__(self):
		return chain.from_iterable(list(map(reversed, reversed(self._lists))))

	def reverse(self):
		raise NotImplementedError('use ``reversed(sl)`` instead')

	def islice(self, start=None, stop=None, reverse=False):
		_len = self._len
		if not _len:
			return iter(())
		(start, stop, _) = slice(start, stop).indices(self._len)
		if start >= stop:
			return iter(())
		_pos = self._pos
		(min_pos, min_idx) = _pos(start)
		if stop == _len:
			max_pos = len(self._lists) - 1
			max_idx = len(self._lists[-1])
		else:
			(max_pos, max_idx) = _pos(stop)
		return self._islice(min_pos, min_idx, max_pos, max_idx, reverse)

	def _islice(self, min_pos, min_idx, max_pos, max_idx, reverse):
		_lists = self._lists
		if min_pos > max_pos:
			return iter(())
		if min_pos == max_pos:
			if reverse:
				indices = reversed(list(range(min_idx, max_idx)))
				return list(map(_lists[min_pos].__getitem__, indices))
			indices = list(range(min_idx, max_idx))
			return list(map(_lists[min_pos].__getitem__, indices))
		next_pos = min_pos + 1
		if next_pos == max_pos:
			if reverse:
				min_indices = list(range(min_idx, len(_lists[min_pos])))
				max_indices = list(range(max_idx))
				return chain(list(map(_lists[max_pos].__getitem__, reversed(max_indices))), list(map(_lists[min_pos].__getitem__, reversed(min_indices))))
			min_indices = list(range(min_idx, len(_lists[min_pos])))
			max_indices = list(range(max_idx))
			return chain(list(map(_lists[min_pos].__getitem__, min_indices)), list(map(_lists[max_pos].__getitem__, max_indices)))
		if reverse:
			min_indices = list(range(min_idx, len(_lists[min_pos])))
			sublist_indices = list(range(next_pos, max_pos))
			sublists = list(map(_lists.__getitem__, reversed(sublist_indices)))
			max_indices = list(range(max_idx))
			return chain(list(map(_lists[max_pos].__getitem__, reversed(max_indices))), chain.from_iterable(list(map(reversed, sublists))), list(map(_lists[min_pos].__getitem__, reversed(min_indices))))
		min_indices = list(range(min_idx, len(_lists[min_pos])))
		sublist_indices = list(range(next_pos, max_pos))
		sublists = list(map(_lists.__getitem__, sublist_indices))
		max_indices = list(range(max_idx))
		return chain(list(map(_lists[min_pos].__getitem__, min_indices)), chain.from_iterable(sublists), list(map(_lists[max_pos].__getitem__, max_indices)))

	def irange(self, minimum=None, maximum=None, inclusive=(True, True), reverse=False):
		_maxes = self._maxes
		if not _maxes:
			return iter(())
		_lists = self._lists
		if minimum is None:
			min_pos = 0
			min_idx = 0
		elif inclusive[0]:
			min_pos = bisect_left(_maxes, minimum)
			if min_pos == len(_maxes):
				return iter(())
			min_idx = bisect_left(_lists[min_pos], minimum)
		else:
			min_pos = bisect_right(_maxes, minimum)
			if min_pos == len(_maxes):
				return iter(())
			min_idx = bisect_right(_lists[min_pos], minimum)
		if maximum is None:
			max_pos = len(_maxes) - 1
			max_idx = len(_lists[max_pos])
		elif inclusive[1]:
			max_pos = bisect_right(_maxes, maximum)
			if max_pos == len(_maxes):
				max_pos -= 1
				max_idx = len(_lists[max_pos])
			else:
				max_idx = bisect_right(_lists[max_pos], maximum)
		else:
			max_pos = bisect_left(_maxes, maximum)
			if max_pos == len(_maxes):
				max_pos -= 1
				max_idx = len(_lists[max_pos])
			else:
				max_idx = bisect_left(_lists[max_pos], maximum)
		return self._islice(min_pos, min_idx, max_pos, max_idx, reverse)

	def __len__(self):
		return self._len

	def bisect_left(self, value):
		_maxes = self._maxes
		if not _maxes:
			return 0
		pos = bisect_left(_maxes, value)
		if pos == len(_maxes):
			return self._len
		idx = bisect_left(self._lists[pos], value)
		return self._loc(pos, idx)

	def bisect_right(self, value):
		_maxes = self._maxes
		if not _maxes:
			return 0
		pos = bisect_right(_maxes, value)
		if pos == len(_maxes):
			return self._len
		idx = bisect_right(self._lists[pos], value)
		return self._loc(pos, idx)
	bisect = bisect_right
	_bisect_right = bisect_right

	def count(self, value):
		_maxes = self._maxes
		if not _maxes:
			return 0
		pos_left = bisect_left(_maxes, value)
		if pos_left == len(_maxes):
			return 0
		_lists = self._lists
		idx_left = bisect_left(_lists[pos_left], value)
		pos_right = bisect_right(_maxes, value)
		if pos_right == len(_maxes):
			return self._len - self._loc(pos_left, idx_left)
		idx_right = bisect_right(_lists[pos_right], value)
		if pos_left == pos_right:
			return idx_right - idx_left
		right = self._loc(pos_right, idx_right)
		left = self._loc(pos_left, idx_left)
		return right - left

	def copy(self):
		return self.__class__(self)
	__copy__ = copy

	def append(self, value):
		raise NotImplementedError('use ``sl.add(value)`` instead')

	def extend(self, values):
		raise NotImplementedError('use ``sl.update(values)`` instead')

	def insert(self, index, value):
		raise NotImplementedError('use ``sl.add(value)`` instead')

	def pop(self, index=-1):
		if not self._len:
			raise IndexError('pop index out of range')
		_lists = self._lists
		if index == 0:
			val = _lists[0][0]
			self._delete(0, 0)
			return val
		if index == -1:
			pos = len(_lists) - 1
			loc = len(_lists[pos]) - 1
			val = _lists[pos][loc]
			self._delete(pos, loc)
			return val
		if 0 <= index < len(_lists[0]):
			val = _lists[0][index]
			self._delete(0, index)
			return val
		len_last = len(_lists[-1])
		if -len_last < index < 0:
			pos = len(_lists) - 1
			loc = len_last + index
			val = _lists[pos][loc]
			self._delete(pos, loc)
			return val
		(pos, idx) = self._pos(index)
		val = _lists[pos][idx]
		self._delete(pos, idx)
		return val

	def index(self, value, start=None, stop=None):
		_len = self._len
		if not _len:
			raise ValueError('{0!r} is not in list'.format(value))
		if start is None:
			start = 0
		if start < 0:
			start += _len
		if start < 0:
			start = 0
		if stop is None:
			stop = _len
		if stop < 0:
			stop += _len
		if stop > _len:
			stop = _len
		if stop <= start:
			raise ValueError('{0!r} is not in list'.format(value))
		_maxes = self._maxes
		pos_left = bisect_left(_maxes, value)
		if pos_left == len(_maxes):
			raise ValueError('{0!r} is not in list'.format(value))
		_lists = self._lists
		idx_left = bisect_left(_lists[pos_left], value)
		if _lists[pos_left][idx_left] != value:
			raise ValueError('{0!r} is not in list'.format(value))
		stop -= 1
		left = self._loc(pos_left, idx_left)
		if start <= left:
			if left <= stop:
				return left
		else:
			right = self._bisect_right(value) - 1
			if start <= right:
				return start
		raise ValueError('{0!r} is not in list'.format(value))

	def __add__(self, other):
		values = reduce(iadd, self._lists, [])
		values.extend(other)
		return self.__class__(values)
	__radd__ = __add__

	def __iadd__(self, other):
		self._update(other)
		return self

	def __mul__(self, num):
		values = reduce(iadd, self._lists, []) * num
		return self.__class__(values)
	__rmul__ = __mul__

	def __imul__(self, num):
		values = reduce(iadd, self._lists, []) * num
		self._clear()
		self._update(values)
		return self

	def __make_cmp(seq_op, symbol, doc):

		def comparer(self, other):
			if not isinstance(other, Sequence):
				return NotImplemented
			self_len = self._len
			len_other = len(other)
			if self_len != len_other:
				if seq_op is eq:
					return False
				if seq_op is ne:
					return True
			for (alpha, beta) in zip(self, other):
				if alpha != beta:
					return seq_op(alpha, beta)
			return seq_op(self_len, len_other)
		seq_op_name = seq_op.__name__
		comparer.__name__ = '__{0}__'.format(seq_op_name)
		doc_str = 'Return true if and only if sorted list is {0} `other`.\n\n        ``sl.__{1}__(other)`` <==> ``sl {2} other``\n\n        Comparisons use lexicographical order as with sequences.\n\n        Runtime complexity: `O(n)`\n\n        :param other: `other` sequence\n        :return: true if sorted list is {0} `other`\n\n        '
		comparer.__doc__ = dedent(doc_str.format(doc, seq_op_name, symbol))
		return comparer
	__eq__ = __make_cmp(eq, '==', 'equal to')
	__ne__ = __make_cmp(ne, '!=', 'not equal to')
	__lt__ = __make_cmp(lt, '<', 'less than')
	__gt__ = __make_cmp(gt, '>', 'greater than')
	__le__ = __make_cmp(le, '<=', 'less than or equal to')
	__ge__ = __make_cmp(ge, '>=', 'greater than or equal to')
	__make_cmp = staticmethod(__make_cmp)

	def __reduce__(self):
		values = reduce(iadd, self._lists, [])
		return (type(self), (values,))

	@recursive_repr()
	def __repr__(self):
		return '{0}({1!r})'.format(type(self).__name__, list(self))

	def _check(self):
		try:
			assert self._load >= 4
			assert len(self._maxes) == len(self._lists)
			assert self._len == sum((len(sublist) for sublist in self._lists))
			for sublist in self._lists:
				for pos in range(1, len(sublist)):
					assert sublist[pos - 1] <= sublist[pos]
			for pos in range(1, len(self._lists)):
				assert self._lists[pos - 1][-1] <= self._lists[pos][0]
			for pos in range(len(self._maxes)):
				assert self._maxes[pos] == self._lists[pos][-1]
			double = self._load << 1
			assert all((len(sublist) <= double for sublist in self._lists))
			half = self._load >> 1
			for pos in range(0, len(self._lists) - 1):
				assert len(self._lists[pos]) >= half
			if self._index:
				assert self._len == self._index[0]
				assert len(self._index) == self._offset + len(self._lists)
				for pos in range(len(self._lists)):
					leaf = self._index[self._offset + pos]
					assert leaf == len(self._lists[pos])
				for pos in range(self._offset):
					child = (pos << 1) + 1
					if child >= len(self._index):
						assert self._index[pos] == 0
					elif child + 1 == len(self._index):
						assert self._index[pos] == self._index[child]
					else:
						child_sum = self._index[child] + self._index[child + 1]
						assert child_sum == self._index[pos]
		except:
			traceback.print_exc(file=sys.stdout)
			print('len', self._len)
			print('load', self._load)
			print('offset', self._offset)
			print('len_index', len(self._index))
			print('index', self._index)
			print('len_maxes', len(self._maxes))
			print('maxes', self._maxes)
			print('len_lists', len(self._lists))
			print('lists', self._lists)
			raise
(n, q) = list(map(int, input().split()))
pp = list(map(int, input().split()))
sl = SortedList(pp)
h = SortedList((x - y for (x, y) in zip(sl[1:], sl)))
h.add(0)
print(sl[-1] - sl[0] - h[-1], flush=False)
for _ in range(q):
	(t, x) = list(map(int, input().split()))
	if t == 0:
		i = sl.bisect_left(x)
		if len(sl) > 1:
			if i == 0:
				r = sl[i + 1] - x
				h.remove(r)
			elif i == len(sl) - 1:
				l = x - sl[i - 1]
				h.remove(l)
			else:
				l = x - sl[i - 1]
				r = sl[i + 1] - x
				h.remove(l)
				h.remove(r)
				h.add(l + r)
		del sl[i]
	else:
		i = sl.bisect(x)
		if sl:
			if i == 0:
				r = sl[i] - x
				h.add(r)
			elif i == len(sl):
				l = x - sl[i - 1]
				h.add(l)
			else:
				l = x - sl[i - 1]
				r = sl[i] - x
				h.remove(l + r)
				h.add(l)
				h.add(r)
		sl.add(x)
	if sl:
		print(sl[-1] - sl[0] - h[-1], flush=False)
	else:
		print(0, flush=False)


import os
import sys
from io import BytesIO, IOBase
_str = str
BUFSIZE = 8192

def str(x=b''):
	return x if type(x) is bytes else _str(x).encode()

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')

def inp():
	return sys.stdin.readline().rstrip()

def mpint():
	return map(int, inp().split(' '))

def itg():
	return int(inp())

class FenwickTree:

	def __init__(self, x=[]):
		self.bit = x
		for i in range(len(x)):
			j = i | i + 1
			if j < len(x):
				x[j] += x[i]

	def update(self, idx, x):
		while idx < len(self.bit):
			self.bit[idx] += x
			idx |= idx + 1

	def query(self, end):
		x = 0
		while end:
			x += self.bit[end - 1]
			end &= end - 1
		return x

	def findkth(self, k):
		idx = -1
		for d in reversed(range(len(self.bit).bit_length())):
			right_idx = idx + (1 << d)
			if right_idx < len(self.bit) and k >= self.bit[right_idx]:
				idx = right_idx
				k -= self.bit[idx]
		return idx + 1
from heapq import heappop, heappush

class Transform(int):

	def __lt__(self, other):
		return self >= other

class DiscreteSortedList:

	def __init__(self, discrete_data):
		self.restore = discrete_data
		self.DISCRETE_SIZE = len(self.restore)
		self._len = 0
		self.discrete_dict = dict(zip(self.restore, range(self.DISCRETE_SIZE)))
		self._fen = FenwickTree([0] * (self.DISCRETE_SIZE + 1))
		self.nums = [0] * (self.DISCRETE_SIZE + 1)

	def update(self, val, num=1):
		val = self.discrete_dict[val]
		if num < -self.nums[val]:
			num = -self.nums[val]
		self.nums[val] += num
		self._len += num
		self._fen.update(val, num)

	def clear(self):
		self.nums = [0] * (self.DISCRETE_SIZE + 1)
		self._fen.bit = [0] * (self.DISCRETE_SIZE + 1)
		self._len = 0

	def count(self, val):
		return self.nums[self.discrete_dict[val]]

	def bisect_left(self, val):
		return self._fen.query(self.discrete_dict[val])

	def bisect_right(self, val):
		return self._fen.query(self.discrete_dict[val] + 1)

	def __getitem__(self, index):
		if self._len == 0:
			return None
		return self.restore[self._fen.findkth(index % self._len)]

	def lower(self, val):
		index = self.bisect_left(val)
		if index == 0:
			return None
		return self[index - 1]

	def higher(self, val):
		index = self.bisect_right(val)
		if index == self._len:
			return None
		return self[index]

	def to_dict(self):
		result = {}
		val = self[0]
		while val:
			result[val] = self.count(val)
			val = self.higher(val)
		return result

	def __contains__(self, item):
		return self.nums[self.discrete_dict[item]] > 0

	def ceiling(self, val):
		return val if val in self else self.higher(val)

	def floor(self, val):
		return val if val in self else self.lower(val)

	def __iter__(self):
		return (self.__getitem__(index) for index in range(self._len))

	def __repr__(self):
		return 'DiscreteSortedList({})'.format(list(self))

	def __len__(self):
		return self._len

	def __bool__(self):
		return self._len > 0

class RemovableHeap:

	def __init__(self, max_heap_type=None):
		if max_heap_type:

			class Transform(max_heap_type):

				def __lt__(self, other):
					return self >= other
			self._T = Transform
		else:
			self._T = lambda x: x
		self.heap = []
		self.rem = []
		self.dict = {}
		self.size = 0

	def __len__(self):
		return self.size

	def peek(self):
		self.__trim()
		return self.heap[0]

	def push(self, val):
		val = self._T(val)
		heappush(self.heap, val)
		if val in self.dict:
			self.dict[val] += 1
		else:
			self.dict[val] = 1
		self.size += 1

	def pop(self):
		self.__trim()
		if not self.heap:
			return None
		self.size -= 1
		val = heappop(self.heap)
		if self.dict[val] == 1:
			del self.dict[val]
		else:
			self.dict[val] -= 1
		return val

	def remove(self, val):
		val = self._T(val)
		if val not in self.dict:
			return
		self.size -= 1
		if self.dict[val] == 1:
			del self.dict[val]
		else:
			self.dict[val] -= 1
		heappush(self.rem, val)

	def __trim(self):
		while self.rem and self.rem[0] == self.heap[0]:
			heappop(self.heap)
			heappop(self.rem)

def solve():
	(n, q) = mpint()
	arr = sorted(mpint())
	discrete_data = arr.copy()
	input_data = [tuple(mpint()) for _ in range(q)]
	for (t, x) in input_data:
		if t == 1:
			discrete_data.append(x)
	indices = DiscreteSortedList(sorted(set(discrete_data)))
	intervals = RemovableHeap(int)
	for a in arr:
		indices.update(a)
	for i in range(1, n):
		intervals.push(arr[i] - arr[i - 1])

	def query():
		if not intervals:
			return 0
		return indices[-1] - indices[0] - intervals.peek()
	print(query())
	for (t, x) in input_data:
		if t == 0:
			lower = indices.lower(x)
			higher = indices.higher(x)
			if lower:
				intervals.remove(x - lower)
			if higher:
				intervals.remove(higher - x)
			if lower and higher:
				intervals.push(higher - lower)
			indices.update(x, -1)
		else:
			lower = indices.lower(x)
			higher = indices.higher(x)
			if higher and lower:
				intervals.remove(higher - lower)
			if lower:
				intervals.push(x - lower)
			if higher:
				intervals.push(higher - x)
			indices.update(x)
		print(query())

def main():
	solve()
DEBUG = 0
URL = 'https://codeforces.com/contest/1418/problem/D'
if DEBUG == 1:
	import requests
	from ACgenerator.Y_Test_Case_Runner import TestCaseRunner
	runner = TestCaseRunner(main, URL)
	inp = runner.input_stream
	print = runner.output_stream
	runner.checking()
elif DEBUG == 2:
	main()
else:
	(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
	main()


import sys
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep='\n')

def II():
	return int(sys.stdin.readline())

def MI():
	return map(int, sys.stdin.readline().split())

def LI():
	return list(map(int, sys.stdin.readline().split()))

def LLI(rows_number):
	return [LI() for _ in range(rows_number)]

def SI():
	return sys.stdin.readline()[:-1]

class BitSum:

	def __init__(self, n):
		self.n = n + 1
		self.table = [0] * self.n

	def add(self, i, x):
		i += 1
		while i < self.n:
			self.table[i] += x
			i += i & -i

	def sum(self, i):
		i += 1
		res = 0
		while i > 0:
			res += self.table[i]
			i -= i & -i
		return res

	def pos(self, x):
		idx = 0
		for lv in range((self.n - 1).bit_length() - 1, -1, -1):
			mid = idx + (1 << lv)
			if mid >= self.n:
				continue
			if self.table[mid] < x:
				x -= self.table[mid]
				idx += 1 << lv
		return idx

class Cset:

	def __init__(self, aa):
		aa = set(aa)
		self.dec = tuple(sorted(aa))
		self.enc = {a: i for (i, a) in enumerate(self.dec)}
		self.mx = len(self.dec)
		self.size = 0
		self.bit = BitSum(self.mx + 1)
		self.nums = [False] * (self.mx + 1)

	def __repr__(self):
		return ' '.join((str(self[i]) for i in range(self.size)))

	def insert(self, a):
		if a not in self.enc:
			return False
		a = self.enc[a]
		if a < 0 or a > self.mx or self.nums[a]:
			return False
		self.size += 1
		self.bit.add(a, 1)
		self.nums[a] = True
		return True

	def remove(self, value):
		if value not in self.enc:
			return False
		value = self.enc[value]
		if value < 0 or value > self.mx or (not self.nums[value]):
			return False
		self.size -= 1
		self.bit.add(value, -1)
		self.nums[value] = False
		return True

	def erase(self, index):
		i = index
		if i >= self.size or i < -self.size:
			return False
		if i < 0:
			i = self.size + i + 1
		else:
			i += 1
		a = self.bit.pos(i)
		self.size -= 1
		self.bit.add(a, -1)
		self.nums[a] = False
		return True

	def __getitem__(self, i):
		if i >= self.size or i < -self.size:
			return -1
		if i < 0:
			i = self.size + i + 1
		else:
			i += 1
		return self.dec[self.bit.pos(i)]

	def __contains__(self, item):
		return self.nums[self.enc[item]]

	def __len__(self):
		return self.size

	def bisect_left(self, a):
		if a not in self.enc:
			return -1
		a = self.enc[a]
		if a < 0 or a > self.mx:
			return -1
		if a == 0:
			return 0
		return self.bit.sum(a - 1)

	def bisect_right(self, a):
		if a not in self.enc:
			return -1
		a = self.enc[a]
		if a < 0 or a > self.mx:
			return -1
		return self.bit.sum(a)

class RemovableHeap:

	def __init__(self):
		self.hp = []
		self.rem = []
		self.s = {}
		self.size = 0

	def __len__(self):
		return self.size

	def __getitem__(self, i):
		if i:
			return None
		self.__trim()
		return self.hp[0]

	def push(self, val):
		heappush(self.hp, val)
		if val in self.s:
			self.s[val] += 1
		else:
			self.s[val] = 1
		self.size += 1
		return True

	def pop(self):
		self.__trim()
		if not self.hp:
			return None
		self.size -= 1
		val = heappop(self.hp)
		if self.s[val] == 1:
			del self.s[val]
		else:
			self.s[val] -= 1
		return val

	def remove(self, val):
		if val not in self.s:
			return False
		self.size -= 1
		if self.s[val] == 1:
			del self.s[val]
		else:
			self.s[val] -= 1
		heappush(self.rem, val)
		return True

	def __trim(self):
		while self.rem and self.rem[0] == self.hp[0]:
			heappop(self.hp)
			heappop(self.rem)
from heapq import *
mx = 200005
(n, q) = MI()
pp = LI()
tx = LLI(q)
st = Cset(pp + [x for (t, x) in tx])
for p in pp:
	st.insert(p)
pp.sort()
hp = RemovableHeap()
for i in range(n - 1):
	hp.push(-pp[i + 1] + pp[i])
w = pp[-1] - pp[0]
if len(hp):
	print(w + hp[0])
else:
	print(0)
for (t, x) in tx:
	i = st.bisect_left(x)
	if t:
		if i == 0:
			if len(st) > 0:
				p = st[0]
				hp.push(x - p)
				w += p - x
		elif i == len(st):
			p = st[-1]
			hp.push(p - x)
			w += x - p
		else:
			pl = st[i - 1]
			pr = st[i]
			hp.push(pl - x)
			hp.push(x - pr)
			hp.remove(pl - pr)
		st.insert(x)
	else:
		if i == 0:
			if len(st) > 1:
				pl = st[0]
				pr = st[1]
				hp.remove(pl - pr)
				w -= pr - pl
		elif i == len(st) - 1:
			pl = st[-2]
			pr = st[-1]
			hp.remove(pl - pr)
			w -= pr - pl
		else:
			pl = st[i - 1]
			pr = st[i + 1]
			hp.push(pl - pr)
			hp.remove(pl - x)
			hp.remove(x - pr)
		st.remove(x)
	if len(hp):
		print(w + hp[0])
	else:
		print(0)


import sys
sys.setrecursionlimit(10 ** 5)
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep='\n')

def II():
	return int(sys.stdin.readline())

def MI():
	return map(int, sys.stdin.readline().split())

def LI():
	return list(map(int, sys.stdin.readline().split()))

def LLI(rows_number):
	return [LI() for _ in range(rows_number)]

def SI():
	return sys.stdin.readline()[:-1]

class BitSum:

	def __init__(self, n):
		self.n = n + 1
		self.table = [0] * self.n

	def add(self, i, x):
		i += 1
		while i < self.n:
			self.table[i] += x
			i += i & -i

	def sum(self, i):
		i += 1
		res = 0
		while i > 0:
			res += self.table[i]
			i -= i & -i
		return res

	def sumlr(self, l, r):
		if l >= r:
			return 0
		if l == 0:
			return self.sum(r - 1)
		return self.sum(r - 1) - self.sum(l - 1)

	def rank(self, x):
		idx = 0
		for lv in range((self.n - 1).bit_length() - 1, -1, -1):
			mid = idx + (1 << lv)
			if mid >= self.n:
				continue
			if self.table[mid] < x:
				x -= self.table[mid]
				idx += 1 << lv
		return idx
from heapq import *
mx = 200005
(n, q) = MI()
pp = LI()
tx = LLI(q)
pp.sort()
ss = set()
for p in pp:
	ss.add(p)
for (t, x) in tx:
	ss.add(x)
dec = list(sorted(ss))
enc = {p: i for (i, p) in enumerate(dec)}
bit = BitSum(mx)
for p in pp:
	bit.add(enc[p], 1)
hp = []
for i in range(n - 1):
	heappush(hp, -pp[i + 1] + pp[i])
w = pp[-1] - pp[0]
if hp:
	print(w + hp[0])
else:
	print(0)
rem = []
for (t, x) in tx:
	a = enc[x]
	if n == 0:
		bit.add(a, 1)
		n += 1
		print(0)
		continue
	l = bit.sum(a)
	if t:
		if l == 0:
			b = bit.rank(1)
			p = dec[b]
			heappush(hp, x - p)
			w += p - x
		elif l == n:
			b = bit.rank(n)
			p = dec[b]
			heappush(hp, p - x)
			w += x - p
		else:
			bl = bit.rank(l)
			br = bit.rank(l + 1)
			pl = dec[bl]
			pr = dec[br]
			heappush(hp, pl - x)
			heappush(hp, x - pr)
			heappush(rem, pl - pr)
		bit.add(a, 1)
		n += 1
	else:
		if l == 1:
			b = bit.rank(2)
			if b != mx:
				p = dec[b]
				heappush(rem, x - p)
				w -= p - x
		elif l == n:
			b = bit.rank(n - 1)
			p = dec[b]
			heappush(rem, p - x)
			w -= x - p
		else:
			bl = bit.rank(l - 1)
			br = bit.rank(l + 1)
			pl = dec[bl]
			pr = dec[br]
			heappush(rem, pl - x)
			heappush(rem, x - pr)
			heappush(hp, pl - pr)
		n -= 1
		bit.add(a, -1)
	while rem and hp[0] == rem[0]:
		heappop(hp)
		heappop(rem)
	if hp:
		print(w + hp[0])
	else:
		print(0)


import os
import sys
from io import BytesIO, IOBase
_str = str
BUFSIZE = 8192

def str(x=b''):
	return x if type(x) is bytes else _str(x).encode()

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')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))

def inp():
	return sys.stdin.readline()

def mpint():
	return map(int, sys.stdin.readline().split(' '))

def itg():
	return int(sys.stdin.readline())
import random

class TreapMultiSet(object):
	root = 0
	size = 0

	def __init__(self, data):
		self.root = treap_builder(data)
		self.size = len(data)

	def add(self, key):
		self.root = treap_insert(self.root, key)
		self.size += 1

	def remove(self, key):
		self.root = treap_erase(self.root, key)
		self.size -= 1

	def discard(self, key):
		try:
			self.remove(key)
		except KeyError:
			pass

	def ceiling(self, key):
		x = treap_ceiling(self.root, key)
		return treap_keys[x] if x else None

	def higher(self, key):
		x = treap_higher(self.root, key)
		return treap_keys[x] if x else None

	def floor(self, key):
		x = treap_floor(self.root, key)
		return treap_keys[x] if x else None

	def lower(self, key):
		x = treap_lower(self.root, key)
		return treap_keys[x] if x else None

	def max(self):
		return treap_keys[treap_max(self.root)]

	def min(self):
		return treap_keys[treap_min(self.root)]

	def __len__(self):
		return self.size

	def __nonzero__(self):
		return bool(self.root)
	__bool__ = __nonzero__

	def __contains__(self, key):
		return self.floor(key) == key

	def __repr__(self):
		return 'TreapMultiSet({})'.format(list(self))

	def __iter__(self):
		if not self.root:
			return iter([])
		out = []
		stack = [self.root]
		while stack:
			node = stack.pop()
			if node > 0:
				if right_child[node]:
					stack.append(right_child[node])
				stack.append(~node)
				if left_child[node]:
					stack.append(left_child[node])
			else:
				out.append(treap_keys[~node])
		return iter(out)
left_child = [0]
right_child = [0]
treap_keys = [0]
treap_prior = [0.0]

def treap_builder(sorted_data):

	def build(begin, end):
		if begin == end:
			return 0
		mid = (begin + end) // 2
		root = treap_create_node(sorted_data[mid])
		left_child[root] = build(begin, mid)
		right_child[root] = build(mid + 1, end)
		ind = root
		while True:
			lc = left_child[ind]
			rc = right_child[ind]
			if lc and treap_prior[lc] > treap_prior[ind]:
				if rc and treap_prior[rc] > treap_prior[rc]:
					(treap_prior[ind], treap_prior[rc]) = (treap_prior[rc], treap_prior[ind])
					ind = rc
				else:
					(treap_prior[ind], treap_prior[lc]) = (treap_prior[lc], treap_prior[ind])
					ind = lc
			elif rc and treap_prior[rc] > treap_prior[ind]:
				(treap_prior[ind], treap_prior[rc]) = (treap_prior[rc], treap_prior[ind])
				ind = rc
			else:
				break
		return root
	return build(0, len(sorted_data))

def treap_create_node(key):
	treap_keys.append(key)
	treap_prior.append(random.random())
	left_child.append(0)
	right_child.append(0)
	return len(treap_keys) - 1

def treap_split(root, key):
	left_pos = right_pos = 0
	while root:
		if key < treap_keys[root]:
			left_child[right_pos] = right_pos = root
			root = left_child[root]
		else:
			right_child[left_pos] = left_pos = root
			root = right_child[root]
	(left, right) = (right_child[0], left_child[0])
	right_child[left_pos] = left_child[right_pos] = right_child[0] = left_child[0] = 0
	return (left, right)

def treap_merge(left, right):
	(where, pos) = (left_child, 0)
	while left and right:
		if treap_prior[left] > treap_prior[right]:
			where[pos] = pos = left
			where = right_child
			left = right_child[left]
		else:
			where[pos] = pos = right
			where = left_child
			right = left_child[right]
	where[pos] = left or right
	node = left_child[0]
	left_child[0] = 0
	return node

def treap_insert(root, key):
	if not root:
		return treap_create_node(key)
	(left, right) = treap_split(root, key)
	return treap_merge(treap_merge(left, treap_create_node(key)), right)

def treap_insert_unique(root, key):
	if not root:
		return (treap_create_node(key), False)
	(left, right) = treap_split(root, key)
	if left and treap_keys[left] == key:
		return (treap_merge(left, right), True)
	return (treap_merge(treap_merge(left, treap_create_node(key)), right), False)

def treap_erase(root, key):
	if not root:
		raise KeyError(key)
	if treap_keys[root] == key:
		return treap_merge(left_child[root], right_child[root])
	node = root
	while root and treap_keys[root] != key:
		parent = root
		root = left_child[root] if key < treap_keys[root] else right_child[root]
	if not root:
		raise KeyError(key)
	if root == left_child[parent]:
		left_child[parent] = treap_merge(left_child[root], right_child[root])
	else:
		right_child[parent] = treap_merge(left_child[root], right_child[root])
	return node

def treap_ceiling(root, key):
	while root and treap_keys[root] < key:
		root = right_child[root]
	if not root:
		return 0
	min_node = root
	min_key = treap_keys[root]
	while root:
		if treap_keys[root] < key:
			root = right_child[root]
		else:
			if treap_keys[root] < min_key:
				min_key = treap_keys[root]
				min_node = root
			root = left_child[root]
	return min_node

def treap_higher(root, key):
	while root and treap_keys[root] <= key:
		root = right_child[root]
	if not root:
		return 0
	min_node = root
	min_key = treap_keys[root]
	while root:
		if treap_keys[root] <= key:
			root = right_child[root]
		else:
			if treap_keys[root] < min_key:
				min_key = treap_keys[root]
				min_node = root
			root = left_child[root]
	return min_node

def treap_floor(root, key):
	while root and treap_keys[root] > key:
		root = left_child[root]
	if not root:
		return 0
	max_node = root
	max_key = treap_keys[root]
	while root:
		if treap_keys[root] > key:
			root = left_child[root]
		else:
			if treap_keys[root] > max_key:
				max_key = treap_keys[root]
				max_node = root
			root = right_child[root]
	return max_node

def treap_lower(root, key):
	while root and treap_keys[root] >= key:
		root = left_child[root]
	if not root:
		return 0
	max_node = root
	max_key = treap_keys[root]
	while root:
		if treap_keys[root] >= key:
			root = left_child[root]
		else:
			if treap_keys[root] > max_key:
				max_key = treap_keys[root]
				max_node = root
			root = right_child[root]
	return max_node

def treap_min(root):
	if not root:
		raise ValueError('min on empty treap')
	while left_child[root]:
		root = left_child[root]
	return root

def treap_max(root):
	if not root:
		raise ValueError('max on empty treap')
	while right_child[root]:
		root = right_child[root]
	return root
(n, q) = mpint()
arr = sorted(mpint())
treap1 = TreapMultiSet(arr)
treap2 = TreapMultiSet(sorted((arr[i] - arr[i - 1] for i in range(1, n))))

def query():
	if not treap2:
		return 0
	return treap1.max() - treap1.min() - treap2.max()
print(query())
for _ in range(q):
	(t, x) = mpint()
	if t == 0:
		lower = treap1.lower(x)
		higher = treap1.higher(x)
		if lower:
			treap2.remove(x - lower)
		if higher:
			treap2.remove(higher - x)
		if lower and higher:
			treap2.add(higher - lower)
		treap1.remove(x)
	else:
		lower = treap1.lower(x)
		higher = treap1.higher(x)
		if higher and lower:
			treap2.remove(higher - lower)
		if lower:
			treap2.add(x - lower)
		if higher:
			treap2.add(higher - x)
		treap1.add(x)
	print(query())


import os, sys
from io import IOBase, BytesIO
py2 = round(0.5)
if py2:
	from future_builtins import ascii, filter, hex, map, oct, zip
	range = xrange
BUFSIZE = 8192

class FastIO(BytesIO):
	newlines = 0

	def __init__(self, file):
		self._file = file
		self._fd = file.fileno()
		self.writable = 'x' in file.mode or 'w' in file.mode
		self.write = super(FastIO, self).write if self.writable else None

	def _fill(self):
		s = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
		self.seek((self.tell(), self.seek(0, 2), super(FastIO, self).write(s))[0])
		return s

	def read(self):
		while self._fill():
			pass
		return super(FastIO, self).read()

	def readline(self):
		while self.newlines == 0:
			s = self._fill()
			self.newlines = s.count(b'\n') + (not s)
		self.newlines -= 1
		return super(FastIO, self).readline()

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

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		if py2:
			self.write = self.buffer.write
			self.read = self.buffer.read
			self.readline = self.buffer.readline
		else:
			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')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
import sys

class ostream:

	def __lshift__(self, a):
		sys.stdout.write(str(a))
		return self
cout = ostream()
endl = '\n'

def get_input(a=str):
	return a(input())

def get_int_input():
	return get_input(int)

def get_input_arr(a):
	return list(map(a, input().split()))

def get_int_input_arr():
	return get_input_arr(int)

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))
import bisect

def solve():
	(n, q) = get_int_input_arr()
	trash = get_int_input_arr()
	trash.sort()
	gs = []
	if len(trash) == 1:
		cout << 0 << endl
	else:
		for i in range(len(trash) - 1):
			gs.append(trash[i] - trash[i + 1])
		gs.sort()
		cout << trash[-1] - trash[0] + gs[0] << endl
	tr = SortedList(trash)
	gaps = SortedList(gs)
	for _ in range(q):
		(q_type, val) = get_int_input_arr()
		if q_type == 1:
			if len(tr) <= 1:
				tr.add(val)
				if len(tr) > 1:
					gaps.add(tr[0] - tr[1])
				cout << 0 << endl
			else:
				pos = bisect.bisect_left(tr, val)
				if pos > 0:
					g1 = tr[pos - 1] - val
					gaps.add(g1)
				if pos < len(tr):
					g2 = val - tr[pos]
					gaps.add(g2)
				if 0 < pos < len(tr):
					g3 = tr[pos - 1] - tr[pos]
					gaps.remove(g3)
				tr.add(val)
				cout << tr[-1] - tr[0] + gaps[0] << endl
		elif len(tr) <= 2:
			if len(tr) > 1:
				gaps = SortedList([])
			tr.remove(val)
			cout << 0 << endl
		else:
			pos = bisect.bisect_left(tr, val)
			if pos > 0:
				g1 = tr[pos - 1] - tr[pos]
				gaps.remove(g1)
			if pos < len(tr) - 1:
				g2 = val - tr[pos + 1]
				gaps.remove(g2)
			if 0 < pos < len(tr) - 1:
				gaps.add(tr[pos - 1] - tr[pos + 1])
			tr.remove(val)
			cout << tr[-1] - tr[0] + gaps[0] << endl

def main():
	solve()
main()


import os
import sys
from io import BytesIO, IOBase
from types import GeneratorType
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		import os
		self.os = os
		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 = self.os.read(self._fd, max(self.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 = self.os.read(self._fd, max(self.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:
			self.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')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
import time
start_time = time.time()
import collections as col, math

def getInts():
	return [int(s) for s in input().split()]

def getInt():
	return int(input())

def getStrs():
	return [s for s in input().split()]

def getStr():
	return input()

def listStr():
	return list(input())

def solve():

	def build(arr):
		for i in range(n):
			x = arr[i]
			tree[n + i] = (counts[x], x, x, 0)
		for i in range(n - 1, 0, -1):
			(a, b) = (tree[i << 1], tree[i << 1 | 1])
			if a[0] == 0:
				tree[i] = b
			elif b[0] == 0:
				tree[i] = a
			else:
				if i << 1 == 2 and a[2] > b[2] and (a[0] > 0):
					gap = tree2[1][1] - b[2]
				else:
					gap = b[1] - a[2]
				tree[i] = (a[0] + b[0], min(a[1], b[1]), max(a[2], b[2]), max(a[3], b[3], gap))

	def updateTreeNode(p, value):
		counts[p] = value
		tree[points_index[p] + n] = (value, p, p, 0)
		i = points_index[p] + n
		while i > 1:
			i >>= 1
			(a, b) = (tree[i << 1], tree[i << 1 | 1])
			if a[0] == 0:
				tree[i] = b
			elif b[0] == 0:
				tree[i] = a
			else:
				gap = b[1] - a[2]
				tree[i] = (a[0] + b[0], min(a[1], b[1]), max(a[2], b[2]), max(a[3], b[3], gap))
	(n, Q) = getInts()
	P = getInts()
	queries = []
	points = set(P)
	for q in range(Q):
		(t, x) = getInts()
		queries.append((t, x))
		points.add(x)
	counts = col.defaultdict(int)
	for p in P:
		counts[p] = 1
	points = sorted(list(points))
	points_index = col.defaultdict(int)
	n = len(points)
	two_pow = 1
	while two_pow <= 2 * n:
		two_pow *= 2
	n = two_pow // 2
	j = 10 ** 10
	while len(points) < n:
		points.append(j + x)
		j += 1
	tree = [0] * two_pow
	build(points)
	for (i, point) in enumerate(points):
		points_index[point] = i
	print(tree[1][2] - tree[1][1] - tree[1][3])
	for (t, x) in queries:
		updateTreeNode(x, t)
		print(tree[1][2] - tree[1][1] - tree[1][3])
	return
solve()


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))
import os
import sys
from io import BytesIO, IOBase
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')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
from math import gcd, ceil

def prod(a, mod=10 ** 9 + 7):
	ans = 1
	for each in a:
		ans = ans * each % mod
	return ans

def lcm(a, b):
	return a * b // gcd(a, b)

def binary(x, length=16):
	y = bin(x)[2:]
	return y if len(y) >= length else '0' * (length - len(y)) + y
for _ in range(int(input()) if not True else 1):
	(n, q) = map(int, input().split())
	a = sorted(list(map(int, input().split())))
	sl = SortedList(a)
	sl2 = SortedList([a[i] - a[i - 1] for i in range(1, n)])
	count = n
	for __ in range(q + 1):
		(high, low) = (sl.__getitem__(count - 1) if count else 0, sl.__getitem__(0) if count else 0)
		if __:
			(t, x) = map(int, input().split())
			if t == 1:
				if count == 0:
					pass
				elif x < low:
					sl2.add(low - x)
					low = x
				elif x > high:
					sl2.add(x - high)
					high = x
				else:
					p = sl.__getitem__(sl.bisect_left(x) - 1)
					q = sl.__getitem__(sl.bisect_right(x))
					sl2.add(x - p)
					sl2.add(q - x)
					sl2.remove(q - p)
				count += 1
				sl.add(x)
			else:
				if x == low:
					if count > 1:
						low = sl.__getitem__(1)
						sl2.remove(low - x)
				elif x == high:
					if count > 1:
						high = sl.__getitem__(count - 2)
						sl2.remove(x - high)
				else:
					p = sl.__getitem__(sl.bisect_left(x) - 1)
					q = sl.__getitem__(sl.bisect_right(x))
					sl2.remove(x - p)
					sl2.remove(q - x)
					sl2.add(q - p)
				sl.remove(x)
				count -= 1
		if count <= 2:
			print(0)
			continue
		maxdiff = sl2.__getitem__(count - 2)
		print(high - low - maxdiff)


import os
import sys
from io import BytesIO, IOBase
_str = str
BUFSIZE = 8192

def str(x=b''):
	return x if type(x) is bytes else _str(x).encode()

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')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))

def inp():
	return sys.stdin.readline()

def mpint():
	return map(int, sys.stdin.readline().split(' '))

def itg():
	return int(sys.stdin.readline())
from heapq import *

class Fenwick:

	def __init__(self, x):
		self.bit = [0] * x

	def update(self, idx, x):
		while idx < len(self.bit):
			self.bit[idx] += x
			idx |= idx + 1

	def query(self, end):
		x = 0
		while end:
			x += self.bit[end - 1]
			end &= end - 1
		return x

	def findkth(self, k):
		idx = -1
		for d in reversed(range(len(self.bit).bit_length())):
			right_idx = idx + (1 << d)
			if right_idx < len(self.bit) and k > self.bit[right_idx]:
				idx = right_idx
				k -= self.bit[idx]
		return idx + 1

class Cset:

	def __init__(self, discrete_data):
		discrete_data = set(discrete_data)
		self.restore = tuple(sorted(discrete_data))
		self.max_size = len(self.restore)
		self.size = 0
		self.discrete_dict = dict(zip(self.restore, range(self.max_size)))
		self.bit = Fenwick(self.max_size + 1)
		self.nums = [False] * (self.max_size + 1)

	def __getitem__(self, index):
		return self.restore[self.bit.findkth(index % self.size + 1)]

	def add(self, val):
		if val not in self.discrete_dict:
			return
		val = self.discrete_dict[val]
		if val < 0 or val > self.max_size or self.nums[val]:
			return
		self.size += 1
		self.bit.update(val, 1)
		self.nums[val] = True

	def discard(self, val):
		if val not in self.discrete_dict:
			return
		val = self.discrete_dict[val]
		if val < 0 or val > self.max_size or (not self.nums[val]):
			return
		self.size -= 1
		self.bit.update(val, -1)
		self.nums[val] = False

	def bisect_left(self, val):
		return self.bit.query(self.discrete_dict[val])

	def bisect_right(self, val):
		return self.bit.query(self.discrete_dict[val] + 1)

	def lower(self, val):
		index = self.bisect_left(val)
		if index == 0:
			return None
		return self[index - 1]

	def higher(self, val):
		index = self.bisect_right(val)
		if index == self.size:
			return None
		return self[index]

	def __delitem__(self, index):
		val = self.bit.findkth(index % self.size + 1)
		self.size -= 1
		self.bit.update(val, -1)
		self.nums[val] = False

	def pop(self, index):
		val = self[index]
		del self[index]
		return val

	def __contains__(self, item):
		return self.nums[self.discrete_dict[item]]

	def __iter__(self):
		return (self.__getitem__(index) for index in range(self.size))

	def __repr__(self):
		return 'Cset({})'.format(list(self))

	def __len__(self):
		return self.size

	def __bool__(self):
		return self.size > 0

class RemovableHeap:

	def __init__(self, max_heap_type=None):
		if max_heap_type:

			class Transform(max_heap_type):

				def __lt__(self, other):
					return self >= other
			self._T = Transform
		else:
			self._T = lambda x: x
		self.heap = []
		self.rem = []
		self.dict = {}
		self.size = 0

	def __len__(self):
		return self.size

	def __getitem__(self, index):
		self.__trim()
		return self.heap[index]

	def push(self, val):
		val = self._T(val)
		heappush(self.heap, val)
		if val in self.dict:
			self.dict[val] += 1
		else:
			self.dict[val] = 1
		self.size += 1

	def pop(self):
		self.__trim()
		if not self.heap:
			return None
		self.size -= 1
		val = heappop(self.heap)
		if self.dict[val] == 1:
			del self.dict[val]
		else:
			self.dict[val] -= 1
		return val

	def remove(self, val):
		val = self._T(val)
		if val not in self.dict:
			return
		self.size -= 1
		if self.dict[val] == 1:
			del self.dict[val]
		else:
			self.dict[val] -= 1
		heappush(self.rem, val)

	def __trim(self):
		while self.rem and self.rem[0] == self.heap[0]:
			heappop(self.heap)
			heappop(self.rem)

def solve():
	(n, q) = mpint()
	arr = sorted(mpint())
	discrete_data = arr.copy()
	input_data = [tuple(mpint()) for _ in range(q)]
	for (t, x) in input_data:
		if t == 1:
			discrete_data.append(x)
	indices = Cset(sorted(set(discrete_data)))
	intervals = RemovableHeap(int)
	for a in arr:
		indices.add(a)
	for i in range(1, n):
		intervals.push(arr[i] - arr[i - 1])

	def query():
		if not intervals:
			return 0
		return indices[-1] - indices[0] - intervals[0]
	print(query())
	for (t, x) in input_data:
		if t == 0:
			lower = indices.lower(x)
			higher = indices.higher(x)
			if lower:
				intervals.remove(x - lower)
			if higher:
				intervals.remove(higher - x)
			if lower and higher:
				intervals.push(higher - lower)
			indices.discard(x)
		else:
			lower = indices.lower(x)
			higher = indices.higher(x)
			if higher and lower:
				intervals.remove(higher - lower)
			if lower:
				intervals.push(x - lower)
			if higher:
				intervals.push(higher - x)
			indices.add(x)
		print(query())
solve()


import os
import sys
from io import BytesIO, IOBase
from bisect import bisect_left
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		import os
		self.os = os
		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 = self.os.read(self._fd, max(self.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 = self.os.read(self._fd, max(self.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:
			self.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')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')

def ri():
	return int(input())

def rl():
	return list(map(int, input().split()))

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))

def solve_query():
	if len(pp) > 1:
		print(pp[-1] - pp[0] - distances[-1])
	else:
		print(0)
(n, q) = rl()
pp = rl()
pp = SortedList(pp)
distances = SortedList([pp[i] - pp[i - 1] for i in range(1, n)])
solve_query()
for query in range(q):
	(t, val) = rl()
	if t == 1:
		if len(pp) > 0:
			idx = pp.bisect_left(val)
			if idx == 0:
				distances.add(pp[0] - val)
				pp.add(val)
			elif idx == len(pp):
				distances.add(val - pp[-1])
				pp.add(val)
			else:
				distances.remove(pp[idx] - pp[idx - 1])
				distances.add(pp[idx] - val)
				distances.add(val - pp[idx - 1])
				pp.add(val)
		else:
			pp.add(val)
	else:
		pp.remove(val)
		if len(pp) > 0:
			idx = pp.bisect_left(val)
			if idx == 0:
				distances.remove(pp[0] - val)
			elif idx == len(pp):
				distances.remove(val - pp[-1])
			else:
				distances.add(pp[idx] - pp[idx - 1])
				distances.remove(pp[idx] - val)
				distances.remove(val - pp[idx - 1])
	solve_query()


import os
import sys
from io import BytesIO, IOBase
import heapq as hq

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))

def main():
	(n, q) = lin()
	a = lin()
	a.sort()
	sl = SortedList(a)
	exists = set()
	arr = []
	for i in range(1, n):
		arr.append([a[i - 1] - a[i], (a[i - 1], a[i])])
		exists.add((a[i - 1], a[i]))
	hq.heapify(arr)

	def get_sol():
		if len(sl) <= 2:
			return 0
		(mn, mx) = (sl[0], sl[-1])
		while arr:
			(sol, pt) = hq.heappop(arr)
			sol = -sol
			if pt in exists:
				hq.heappush(arr, [-sol, pt])
				return mx - mn - sol
		return mx - mn - 0

	def exists_remove(l, r):
		if l < len(sl) and r < len(sl):
			pt = (sl[l], sl[r])
			if pt in exists:
				exists.remove(pt)

	def arr_add(l, r):
		if l < r:
			exists.add((l, r))
			hq.heappush(arr, [l - r, (l, r)])

	def get_l_r(val):
		pos = sl.bisect_left(val)
		(lf, rt) = (pos - 1, pos)
		if lf < 0:
			lf = len(sl)
		return (lf, rt)
	print(get_sol())
	for _ in range(q):
		(Q, val) = lin()
		if Q == 1:
			(l, r) = get_l_r(val)
			exists_remove(l, r)
			ln = len(sl)
			if l < ln:
				L = sl[l]
				arr_add(L, val)
			if r < ln:
				R = sl[r]
				arr_add(val, R)
			sl.add(val)
		else:
			sl.discard(val)
			(l, r) = get_l_r(val)
			ln = len(sl)
			if r < ln:
				R = sl[r]
				if (val, R) in exists:
					exists.remove((val, R))
			if l < ln:
				L = sl[l]
				if (L, val) in exists:
					exists.remove((L, val))
			if l < ln and r < ln:
				L = sl[l]
				R = sl[r]
				arr_add(L, R)
		print(get_sol())
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')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')

def iin():
	return int(input())

def lin():
	return list(map(int, input().split()))
main()


from bisect import bisect_left, bisect_right, insort
from functools import reduce
from operator import add, iadd
from itertools import chain, starmap, repeat
from math import log

class SortedList:
	DEFAULT_LOAD_FACTOR = 1000

	def __init__(self, iterable=None):
		self._len = 0
		self._load = self.DEFAULT_LOAD_FACTOR
		self._lists = []
		self._maxes = []
		self._index = []
		self._offset = 0
		if iterable is not None:
			self.update(iterable)

	def clear(self):
		self._len = 0
		del self._lists[:]
		del self._maxes[:]
		del self._index[:]
		self._offset = 0

	def add(self, value):
		_lists = self._lists
		_maxes = self._maxes
		if _maxes:
			pos = bisect_right(_maxes, value)
			if pos == len(_maxes):
				pos -= 1
				_lists[pos].append(value)
				_maxes[pos] = value
			else:
				insort(_lists[pos], value)
			self._expand(pos)
		else:
			_lists.append([value])
			_maxes.append(value)
		self._len += 1

	def _expand(self, pos):
		_load = self._load
		_lists = self._lists
		_index = self._index
		if len(_lists[pos]) > _load << 1:
			_maxes = self._maxes
			_lists_pos = _lists[pos]
			half = _lists_pos[_load:]
			del _lists_pos[_load:]
			_maxes[pos] = _lists_pos[-1]
			_lists.insert(pos + 1, half)
			_maxes.insert(pos + 1, half[-1])
			del _index[:]
		elif _index:
			child = self._offset + pos
			while child:
				_index[child] += 1
				child = child - 1 >> 1
			_index[0] += 1

	def update(self, iterable):
		_lists = self._lists
		_maxes = self._maxes
		values = sorted(iterable)
		if _maxes:
			if len(values) * 4 >= self._len:
				values.extend(chain.from_iterable(_lists))
				values.sort()
				self.clear()
			else:
				_add = self.add
				for val in values:
					_add(val)
				return
		_load = self._load
		_lists.extend((values[pos:pos + _load] for pos in range(0, len(values), _load)))
		_maxes.extend((sublist[-1] for sublist in _lists))
		self._len = len(values)
		del self._index[:]

	def __contains__(self, value):
		_maxes = self._maxes
		if not _maxes:
			return False
		pos = bisect_left(_maxes, value)
		if pos == len(_maxes):
			return False
		_lists = self._lists
		idx = bisect_left(_lists[pos], value)
		return _lists[pos][idx] == value

	def discard(self, value):
		_maxes = self._maxes
		if not _maxes:
			return
		pos = bisect_left(_maxes, value)
		if pos == len(_maxes):
			return
		_lists = self._lists
		idx = bisect_left(_lists[pos], value)
		if _lists[pos][idx] == value:
			self._delete(pos, idx)

	def remove(self, value):
		_maxes = self._maxes
		if not _maxes:
			raise ValueError('{0!r} not in list'.format(value))
		pos = bisect_left(_maxes, value)
		if pos == len(_maxes):
			raise ValueError('{0!r} not in list'.format(value))
		_lists = self._lists
		idx = bisect_left(_lists[pos], value)
		if _lists[pos][idx] == value:
			self._delete(pos, idx)
		else:
			raise ValueError('{0!r} not in list'.format(value))

	def _delete(self, pos, idx):
		_lists = self._lists
		_maxes = self._maxes
		_index = self._index
		_lists_pos = _lists[pos]
		del _lists_pos[idx]
		self._len -= 1
		len_lists_pos = len(_lists_pos)
		if len_lists_pos > self._load >> 1:
			_maxes[pos] = _lists_pos[-1]
			if _index:
				child = self._offset + pos
				while child > 0:
					_index[child] -= 1
					child = child - 1 >> 1
				_index[0] -= 1
		elif len(_lists) > 1:
			if not pos:
				pos += 1
			prev = pos - 1
			_lists[prev].extend(_lists[pos])
			_maxes[prev] = _lists[prev][-1]
			del _lists[pos]
			del _maxes[pos]
			del _index[:]
			self._expand(prev)
		elif len_lists_pos:
			_maxes[pos] = _lists_pos[-1]
		else:
			del _lists[pos]
			del _maxes[pos]
			del _index[:]

	def _loc(self, pos, idx):
		if not pos:
			return idx
		_index = self._index
		if not _index:
			self._build_index()
		total = 0
		pos += self._offset
		while pos:
			if not pos & 1:
				total += _index[pos - 1]
			pos = pos - 1 >> 1
		return total + idx

	def _pos(self, idx):
		if idx < 0:
			last_len = len(self._lists[-1])
			if -idx <= last_len:
				return (len(self._lists) - 1, last_len + idx)
			idx += self._len
			if idx < 0:
				raise IndexError('list index out of range')
		elif idx >= self._len:
			raise IndexError('list index out of range')
		if idx < len(self._lists[0]):
			return (0, idx)
		_index = self._index
		if not _index:
			self._build_index()
		pos = 0
		child = 1
		len_index = len(_index)
		while child < len_index:
			index_child = _index[child]
			if idx < index_child:
				pos = child
			else:
				idx -= index_child
				pos = child + 1
			child = (pos << 1) + 1
		return (pos - self._offset, idx)

	def _build_index(self):
		row0 = list(map(len, self._lists))
		if len(row0) == 1:
			self._index[:] = row0
			self._offset = 0
			return
		head = iter(row0)
		tail = iter(head)
		row1 = list(starmap(add, zip(head, tail)))
		if len(row0) & 1:
			row1.append(row0[-1])
		if len(row1) == 1:
			self._index[:] = row1 + row0
			self._offset = 1
			return
		size = 2 ** (int(log(len(row1) - 1, 2)) + 1)
		row1.extend(repeat(0, size - len(row1)))
		tree = [row0, row1]
		while len(tree[-1]) > 1:
			head = iter(tree[-1])
			tail = iter(head)
			row = list(starmap(add, zip(head, tail)))
			tree.append(row)
		reduce(iadd, reversed(tree), self._index)
		self._offset = size * 2 - 1

	def __delitem__(self, index):
		if isinstance(index, slice):
			(start, stop, step) = index.indices(self._len)
			if step == 1 and start < stop:
				if start == 0 and stop == self._len:
					return self.clear()
				elif self._len <= 8 * (stop - start):
					values = self.__getitem__(slice(None, start))
					if stop < self._len:
						values += self.__getitem__(slice(stop, None))
					self.clear()
					return self.update(values)
			indices = range(start, stop, step)
			if step > 0:
				indices = reversed(indices)
			(_pos, _delete) = (self._pos, self._delete)
			for index in indices:
				(pos, idx) = _pos(index)
				_delete(pos, idx)
		else:
			(pos, idx) = self._pos(index)
			self._delete(pos, idx)

	def __getitem__(self, index):
		_lists = self._lists
		if isinstance(index, slice):
			(start, stop, step) = index.indices(self._len)
			if step == 1 and start < stop:
				if start == 0 and stop == self._len:
					return reduce(iadd, self._lists, [])
				(start_pos, start_idx) = self._pos(start)
				start_list = _lists[start_pos]
				stop_idx = start_idx + stop - start
				if len(start_list) >= stop_idx:
					return start_list[start_idx:stop_idx]
				if stop == self._len:
					stop_pos = len(_lists) - 1
					stop_idx = len(_lists[stop_pos])
				else:
					(stop_pos, stop_idx) = self._pos(stop)
				prefix = _lists[start_pos][start_idx:]
				middle = _lists[start_pos + 1:stop_pos]
				result = reduce(iadd, middle, prefix)
				result += _lists[stop_pos][:stop_idx]
				return result
			if step == -1 and start > stop:
				result = self.__getitem__(slice(stop + 1, start + 1))
				result.reverse()
				return result
			indices = range(start, stop, step)
			return list((self.__getitem__(index) for index in indices))
		else:
			if self._len:
				if index == 0:
					return _lists[0][0]
				elif index == -1:
					return _lists[-1][-1]
			else:
				raise IndexError('list index out of range')
			if 0 <= index < len(_lists[0]):
				return _lists[0][index]
			len_last = len(_lists[-1])
			if -len_last < index < 0:
				return _lists[-1][len_last + index]
			(pos, idx) = self._pos(index)
			return _lists[pos][idx]

	def __setitem__(self, index, value):
		message = 'use ``del sl[index]`` and ``sl.add(value)`` instead'
		raise NotImplementedError(message)

	def __iter__(self):
		return chain.from_iterable(self._lists)

	def __reversed__(self):
		return chain.from_iterable(map(reversed, reversed(self._lists)))

	def __len__(self):
		return self._len

	def pop(self, index=-1):
		if not self._len:
			raise IndexError('pop index out of range')
		_lists = self._lists
		if index == 0:
			val = _lists[0][0]
			self._delete(0, 0)
			return val
		if index == -1:
			pos = len(_lists) - 1
			loc = len(_lists[pos]) - 1
			val = _lists[pos][loc]
			self._delete(pos, loc)
			return val
		if 0 <= index < len(_lists[0]):
			val = _lists[0][index]
			self._delete(0, index)
			return val
		len_last = len(_lists[-1])
		if -len_last < index < 0:
			pos = len(_lists) - 1
			loc = len_last + index
			val = _lists[pos][loc]
			self._delete(pos, loc)
			return val
		(pos, idx) = self._pos(index)
		val = _lists[pos][idx]
		self._delete(pos, idx)
		return val

	def index(self, value, start=None, stop=None):
		_len = self._len
		if not _len:
			raise ValueError('{0!r} is not in list'.format(value))
		if start is None:
			start = 0
		if start < 0:
			start += _len
		if start < 0:
			start = 0
		if stop is None:
			stop = _len
		if stop < 0:
			stop += _len
		if stop > _len:
			stop = _len
		if stop <= start:
			raise ValueError('{0!r} is not in list'.format(value))
		_maxes = self._maxes
		pos_left = bisect_left(_maxes, value)
		if pos_left == len(_maxes):
			raise ValueError('{0!r} is not in list'.format(value))
		_lists = self._lists
		idx_left = bisect_left(_lists[pos_left], value)
		if _lists[pos_left][idx_left] != value:
			raise ValueError('{0!r} is not in list'.format(value))
		stop -= 1
		left = self._loc(pos_left, idx_left)
		if start <= left:
			if left <= stop:
				return left
		else:
			right = self.bisect_right(value) - 1
			if start <= right:
				return start
		raise ValueError('{0!r} is not in list'.format(value))

	def bisect_right(self, value):
		_maxes = self._maxes
		if not _maxes:
			return 0
		pos = bisect_right(_maxes, value)
		if pos == len(_maxes):
			return self._len
		idx = bisect_right(self._lists[pos], value)
		return self._loc(pos, idx)
(N, Q) = map(int, input().split())
A = list(map(int, input().split()))
AS = SortedList(A)
DS = SortedList()
t = AS[0]
for a in AS[1:]:
	DS.add(a - t)
	t = a
if len(AS) > 2:
	print(AS[-1] - AS[0] - DS[-1])
else:
	print(0)
for _ in range(Q):
	(T, X) = map(int, input().split())
	if T == 0:
		p = AS.index(X)
		if len(AS) > 1:
			if p == 0:
				DS.discard(AS[1] - X)
			elif p == len(AS) - 1:
				DS.discard(X - AS[-2])
			else:
				DS.discard(X - AS[p - 1])
				DS.discard(AS[p + 1] - X)
				DS.add(AS[p + 1] - AS[p - 1])
		AS.pop(p)
	else:
		AS.add(X)
		p = AS.index(X)
		if len(AS) > 1:
			if p == 0:
				DS.add(AS[1] - X)
			elif p == len(AS) - 1:
				DS.add(X - AS[-2])
			else:
				DS.add(X - AS[p - 1])
				DS.add(AS[p + 1] - X)
				DS.discard(AS[p + 1] - AS[p - 1])
	if len(AS) > 2:
		print(AS[-1] - AS[0] - DS[-1])
	else:
		print(0)