Polycarp is a frequent user of the very popular messenger. He's chatting with his friends all the time. He has $n$ friends, numbered from $1$ to $n$.

Recall that a permutation of size $n$ is an array of size $n$ such that each integer from $1$ to $n$ occurs exactly once in this array.

So his recent chat list can be represented with a permutation $p$ of size $n$. $p_1$ is the most recent friend Polycarp talked to, $p_2$ is the second most recent and so on.

Initially, Polycarp's recent chat list $p$ looks like $1, 2, \dots, n$ (in other words, it is an identity permutation).

After that he receives $m$ messages, the $j$-th message comes from the friend $a_j$. And that causes friend $a_j$ to move to the first position in a permutation, shifting everyone between the first position and the current position of $a_j$ by $1$. Note that if the friend $a_j$ is in the first position already then nothing happens.

For example, let the recent chat list be $p = [4, 1, 5, 3, 2]$:   if he gets messaged by friend $3$, then $p$ becomes $[3, 4, 1, 5, 2]$;  if he gets messaged by friend $4$, then $p$ doesn't change $[4, 1, 5, 3, 2]$;  if he gets messaged by friend $2$, then $p$ becomes $[2, 4, 1, 5, 3]$. 

For each friend consider all position he has been at in the beginning and after receiving each message. Polycarp wants to know what were the minimum and the maximum positions.


-----Input-----

The first line contains two integers $n$ and $m$ ($1 \le n, m \le 3 \cdot 10^5$) — the number of Polycarp's friends and the number of received messages, respectively.

The second line contains $m$ integers $a_1, a_2, \dots, a_m$ ($1 \le a_i \le n$) — the descriptions of the received messages.


-----Output-----

Print $n$ pairs of integers. For each friend output the minimum and the maximum positions he has been in the beginning and after receiving each message.


-----Examples-----
Input
5 4
3 5 1 4

Output
1 3
2 5
1 4
1 5
1 5

Input
4 3
1 2 4

Output
1 3
1 2
3 4
1 4



-----Note-----

In the first example, Polycarp's recent chat list looks like this:   $[1, 2, 3, 4, 5]$  $[3, 1, 2, 4, 5]$  $[5, 3, 1, 2, 4]$  $[1, 5, 3, 2, 4]$  $[4, 1, 5, 3, 2]$ 

So, for example, the positions of the friend $2$ are $2, 3, 4, 4, 5$, respectively. Out of these $2$ is the minimum one and $5$ is the maximum one. Thus, the answer for the friend $2$ is a pair $(2, 5)$.

In the second example, Polycarp's recent chat list looks like this:   $[1, 2, 3, 4]$  $[1, 2, 3, 4]$  $[2, 1, 3, 4]$  $[4, 2, 1, 3]$

Difficulty: MEDIUM

Starter code:

Solutions:
import sys

class BIT:

	def __init__(self, n):
		self.tree = [0] * n
		self.N = n

	def add(self, i, value=1):
		(N, tree) = (self.N, self.tree)
		while i < N:
			tree[i] += value
			i |= i + 1

	def sum(self, r):
		(N, tree) = (self.N, self.tree)
		result = 0
		while r > 0:
			result += tree[r - 1]
			r &= r - 1
		return result
input = sys.stdin.readline
(n, m) = map(int, input().split())
queries = [int(x) - 1 for x in input().split()]
bit = BIT(n + m)
pos = list(reversed(range(n)))
for i in range(n):
	bit.add(i)
mins = list(range(n))
maxs = list(range(n))
for (i, q) in enumerate(queries):
	p = pos[q]
	bit.add(p, value=-1)
	mins[q] = 0
	maxs[q] = max(maxs[q], n - 1 - bit.sum(p))
	p = n + i
	bit.add(p)
	pos[q] = p
for (i, p) in enumerate(pos):
	maxs[i] = max(maxs[i], n - 1 - bit.sum(p))
for i in range(n):
	sys.stdout.write(f'{mins[i] + 1} {maxs[i] + 1}\n')


import sys
import bisect

def LI():
	return [int(x) for x in sys.stdin.readline().split()]
mod = 1000000007

def solve():

	def add(i, x):
		while i < len(bit):
			bit[i] += x
			i += i & -i

	def sum(i):
		res = 0
		while i > 0:
			res += bit[i]
			i -= i & -i
		return res
	(n, m) = LI()
	a = LI()
	bit = [0] * (n + m + 2)
	MIN = [i + 1 for i in range(n)]
	MAX = [i + 1 for i in range(n)]
	f = [i + m + 1 for i in range(n)]
	for i in range(n):
		add(f[i], 1)
	M = m
	for i in range(m):
		ai = a[i] - 1
		MIN[ai] = 1
		index = sum(f[ai])
		if MAX[ai] < index:
			MAX[ai] = index
		add(M, 1)
		add(f[ai], -1)
		f[ai] = M
		M -= 1
	for i in range(n):
		index = sum(f[i])
		if MAX[i] < index:
			MAX[i] = index
	for i in range(n):
		print(MIN[i], MAX[i])
	return
solve()


from __future__ import division, print_function
from bisect import bisect_left
import os
import sys
from io import BytesIO, IOBase
if sys.version_info[0] < 3:
	from __builtin__ import xrange as range
	from future_builtins import ascii, filter, hex, map, oct, zip
alphabets = list('abcdefghijklmnopqrstuvwxyz')

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, m) = [int(x) for x in input().split()]
	a = [int(x) for x in input().split()]
	minans = [3 * 100000] * (n + 1)
	maxans = [0] * (n + 1)
	s = SortedList()
	prev = [10000000.0] * (n + 1)
	cur = 10000000.0
	for i in range(1, n + 1):
		s.add((cur, i))
	for i in a:
		minans[i] = 1
		element = (prev[i], i)
		pos = s.bisect_left(element)
		maxans[i] = max(maxans[i], pos + 1)
		s.remove(element)
		cur -= 1
		prev[i] = cur
		s.add((cur, i))
	for i in range(1, n + 1):
		element = s[i - 1][1]
		minans[element] = min(minans[element], i, element)
		maxans[element] = max(maxans[element], i)
	for i in range(1, n + 1):
		print(minans[i], maxans[i])
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))
input = lambda : sys.stdin.readline().rstrip('\r\n')
main()


(N, M) = map(int, input().split())
pos = [0] * (N + 1)
content = [0] * (N + M + 2)
maxes = list(range(N + 1))
dialogs = set()
message = list(map(int, input().split()))
for i in range(N):
	pos[i + 1] = i + M + 1
	content[i + M + 1] = i + 1

class Fenwick:

	def __init__(self, _size):
		self._size = _size
		self.tree = [0] * _size

	def sum(self, right):
		result = 0
		while right >= 0:
			result += self.tree[right]
			right = (right & right + 1) - 1
		return result

	def add(self, idx, delta):
		while idx < self._size:
			self.tree[idx] += delta
			idx |= idx + 1
fw = Fenwick(N + M + 2)
for i in range(1, N + 1):
	fw.add(pos[i], 1)
front = M + 1
for ms in message:
	if pos[ms] != front:
		maxes[ms] = max(maxes[ms], fw.sum(pos[ms]))
		dialogs.add(ms)
		content[pos[ms]] = 0
		fw.add(pos[ms], -1)
		front -= 1
		pos[ms] = front
		content[pos[ms]] = ms
		fw.add(pos[ms], 1)
mines = list(range(N + 1))
order = 1
for i in range(N + M + 2):
	if content[i] != 0:
		maxes[content[i]] = max(order, maxes[content[i]])
		order += 1
for dia in dialogs:
	mines[dia] = 1
order = 1
for i in range(1, N + 1):
	print(mines[i], maxes[i])


(n, m) = map(int, input().split())
a = [int(i) - 1 for i in input().split()]
ans1 = [i + 1 for i in range(n)]
ans2 = [-1 for i in range(n)]
for i in set(a):
	ans1[i] = 1
N = 1
while N < n + m:
	N <<= 1
st = [0 for i in range(N << 1)]
pos = [i + m for i in range(n)]
for i in range(n):
	st[i + N + m] = 1
for i in range(N - 1, 0, -1):
	st[i] = st[i << 1] + st[i << 1 | 1]

def up(i, v):
	i += N
	st[i] = v
	i >>= 1
	while i > 0:
		st[i] = st[i << 1] + st[i << 1 | 1]
		i >>= 1

def qr(l, r=N):
	l += N
	r += N
	add = 0
	while l < r:
		if l & 1:
			add += st[l]
			l += 1
		if r & 1:
			add += st[r]
			r -= 1
		l >>= 1
		r >>= 1
	return add
for j in range(m):
	x = a[j]
	i = pos[x]
	ans2[x] = max(ans2[x], n - qr(i + 1))
	up(i, 0)
	pos[x] = m - 1 - j
	up(pos[x], 1)
for i in range(n):
	x = pos[i]
	ans2[i] = max(ans2[i], n - qr(x + 1))
for i in range(n):
	print(ans1[i], ans2[i])


class SegmentTree:

	def __init__(self, arr, func, initialRes=0):
		self.f = func
		self.N = len(arr)
		self.tree = [0 for _ in range(4 * self.N)]
		self.initialRes = initialRes
		for i in range(self.N):
			self.tree[self.N + i] = arr[i]
		for i in range(self.N - 1, 0, -1):
			self.tree[i] = self.f(self.tree[i << 1], self.tree[i << 1 | 1])

	def updateTreeNode(self, idx, value):
		self.tree[idx + self.N] = value
		idx += self.N
		i = idx
		while i > 1:
			self.tree[i >> 1] = self.f(self.tree[i], self.tree[i ^ 1])
			i >>= 1

	def query(self, l, r):
		r += 1
		res = self.initialRes
		l += self.N
		r += self.N
		while l < r:
			if l & 1:
				res = self.f(res, self.tree[l])
				l += 1
			if r & 1:
				r -= 1
				res = self.f(res, self.tree[r])
			l >>= 1
			r >>= 1
		return res

def getMaxSegTree(arr):
	return SegmentTree(arr, lambda a, b: max(a, b), initialRes=-float('inf'))

def getMinSegTree(arr):
	return SegmentTree(arr, lambda a, b: min(a, b), initialRes=float('inf'))

def getSumSegTree(arr):
	return SegmentTree(arr, lambda a, b: a + b, initialRes=0)

def main():
	(n, m) = readIntArr()
	a = readIntArr()
	indexes = [-1 for _ in range(n + 1)]
	j = m
	for i in range(1, n + 1):
		indexes[i] = j
		j += 1
	gaps = [1] * m + [0] * n
	st = getSumSegTree(gaps)
	mins = [inf for _ in range(n + 1)]
	maxes = [-inf for _ in range(n + 1)]
	for i in range(1, n + 1):
		mins[i] = indexes[i] - m
		maxes[i] = indexes[i] - m
	left = m
	for p in a:
		mins[p] = 0
		idx = indexes[p]
		gapCnts = st.query(0, idx)
		right = idx - gapCnts
		maxes[p] = max(maxes[p], right)
		st.updateTreeNode(idx, 1)
		st.updateTreeNode(left - 1, 0)
		indexes[p] = left - 1
		left -= 1
	for p in range(1, n + 1):
		idx = indexes[p]
		gapCnts = st.query(0, idx)
		right = idx - gapCnts
		maxes[p] = max(maxes[p], right)
	allans = []
	for p in range(1, n + 1):
		allans.append([mins[p] + 1, maxes[p] + 1])
	multiLineArrayOfArraysPrint(allans)
	return
import sys
input = sys.stdin.buffer.readline

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

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

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

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

def makeArr(*args):
	assert len(args) >= 2, 'makeArr args should be (default value, dimension 1, dimension 2,...'
	if len(args) == 2:
		return [args[0] for _ in range(args[1])]
	else:
		return [makeArr(args[0], *args[2:]) for _ in range(args[1])]

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

def answerInteractive(ans):
	print('! {}'.format(ans))
	sys.stdout.flush()
inf = float('inf')
MOD = 10 ** 9 + 7
for _abc in range(1):
	main()


import collections
import time
import os
import sys
import bisect
import heapq
from typing import List

def solve(N, M, A):
	pos = [i + M for i in range(N + 1)]
	minpos = [i for i in range(N + 1)]
	maxpos = [i for i in range(N + 1)]
	bits = [0 for _ in range(N + M + 1)]

	def add(index, val):
		while index <= N + M:
			bits[index] += val
			index |= index + 1

	def query(index):
		s = 0
		while index >= 0:
			s += bits[index]
			index = (index & index + 1) - 1
		return s
	for i in range(1, N + 1):
		add(i + M, 1)
	first = M
	for v in A:
		minpos[v] = 1
		maxpos[v] = max(maxpos[v], query(pos[v] - 1) + 1)
		add(pos[v], -1)
		pos[v] = first
		first -= 1
		add(pos[v], 1)
	for v in range(1, N + 1):
		maxpos[v] = max(maxpos[v], query(pos[v] - 1) + 1)
	ans = ['{} {}'.format(a, b) for (a, b) in zip(minpos[1:], maxpos[1:])]
	print('\n'.join(ans))
(N, M) = map(int, input().split())
A = [int(x) for x in input().split()]
solve(N, M, A)


import sys
input = sys.stdin.buffer.readline

class FastIntregral:

	def __init__(self, n, *args, **kwargs):
		self.mData = [0 for i in range(n + 1)]
		self.mSize = n

	def upd(self, index, value):
		while index <= self.mSize:
			self.mData[index] += value
			index += index & -index

	def s(self, index):
		res = 0
		while index > 0:
			res += self.mData[index]
			index -= index & -index
		return res
(n, m) = [int(i) for i in input().split()]
T = FastIntregral(m + n + 1)
idx = [i + m for i in range(n + 1)]
ans_min = [False for i in range(n + 1)]
ans_max = [i for i in range(n + 1)]
for i in range(m + 1, n + m + 2):
	T.upd(i, 1)
for q in [int(i) for i in input().split()]:
	ans_min[q] = True
	ans_max[q] = max(ans_max[q], T.s(idx[q]))
	T.upd(idx[q], -1)
	T.upd(m, 1)
	idx[q] = m
	m -= 1
for i in range(1, n + 1):
	print(('1' if ans_min[i] else str(i)) + ' ' + str(max(ans_max[i], T.s(idx[i]))))


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        ``sl.__{1}__(other)`` <==> ``sl {2} other``\n        Comparisons use lexicographical order as with sequences.\n        Runtime complexity: `O(n)`\n        :param other: `other` sequence\n        :return: true if sorted list is {0} `other`\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
import io
import os
from collections import Counter, defaultdict, deque

def solve(N, M, messages):
	ans = [[i, i] for i in range(N)]
	friendsList = SortedList()
	friendsToTime = {i: i for i in range(N)}
	for (f, t) in friendsToTime.items():
		friendsList.add((t, f))
	for (t, f) in enumerate(messages):
		index = friendsList.bisect_left((friendsToTime[f], f))
		ans[f][1] = max(ans[f][1], index)
		friendsList.remove((friendsToTime[f], f))
		friendsToTime[f] = -t - 1
		friendsList.add((friendsToTime[f], f))
		ans[f][0] = min(ans[f][0], 0)
	for (i, (t, f)) in enumerate(friendsList):
		ans[f][0] = min(ans[f][0], i)
		ans[f][1] = max(ans[f][1], i)
	return '\n'.join((str(x + 1) + ' ' + str(y + 1) for (x, y) in ans))
input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline
(N, M) = [int(x) for x in input().split()]
messages = [int(x) - 1 for x in input().split()]
ans = solve(N, M, messages)
print(ans)


class BIT:

	def __init__(self, N):
		self.N = N
		self.tree = [0 for i in range(N)]

	def read(self, idx):
		sum = 0
		while idx > 0:
			sum += self.tree[idx]
			idx -= idx & -idx
		return sum

	def update(self, idx, val):
		while idx < self.N:
			self.tree[idx] += val
			idx += idx & -idx
(n, m) = map(int, input().split())
f = list(map(int, input().split()))
bit = BIT(n + m + 1)
for i in range(1, n + 1):
	bit.update(i, 1)
last = n + 1
mn = [i for i in range(n + 1)]
mx = [0 for i in range(n + 1)]
pos = [n - i + 1 for i in range(n + 1)]
for i in range(m):
	mn[f[i]] = 1
	mx[f[i]] = max(mx[f[i]], n - bit.read(pos[f[i]]) + 1)
	bit.update(pos[f[i]], -1)
	bit.update(last, 1)
	pos[f[i]] = last
	last += 1
for i in range(1, n + 1):
	mx[i] = max(mx[i], n - bit.read(pos[i]) + 1)
	print('{} {}'.format(mn[i], mx[i]))


import sys
input = sys.stdin.readline

def binary_index(ar, n):
	for idx in range(1, n):
		idx2 = idx + (idx & -idx)
		if idx2 < n:
			ar[idx2] += ar[idx]

def update(inp, add, ar, n):
	while inp < n:
		ar[inp] += add
		inp += inp & -inp

def summation(inp, ar):
	ans = 0
	while inp:
		ans += ar[inp]
		inp -= inp & -inp
	return ans
(n, m) = map(int, input().split())
ar = list(map(int, input().split()))
dic = {}
mi = [0]
ma = [0]
for i in range(1, n + 1):
	mi.append(i)
	dic[i] = n - i + 1
	ma.append(dic[i])
li = [0] * (n + m + 1)
for i in range(1, n + 1):
	li[i] = 1
le = n + m + 1
binary_index(li, le)
pointer = n + 1
for i in range(m):
	nu = ar[i]
	mi[nu] = 1
	ind = dic[nu]
	dic[nu] = pointer
	ma[nu] = min(ma[nu], summation(ind, li))
	update(ind, -1, li, le)
	update(pointer, 1, li, le)
	pointer += 1
for i in range(1, n + 1):
	ma[i] = min(ma[i], summation(dic[i], li))
for i in range(1, n + 1):
	print(mi[i], n - ma[i] + 1)


def manager_simulator():

	def add(i, x):
		while i < len(bit):
			bit[i] += x
			i += i & -i

	def sum(i):
		res = 0
		while i > 0:
			res += bit[i]
			i -= i & -i
		return res
	(n, m) = list(map(int, input().split()))
	a = list(map(int, input().split()))
	bit = [0] * (n + m + 2)
	mn = [i + 1 for i in range(n)]
	mx = mn[:]
	f = [i + m + 1 for i in range(n)]
	for i in range(n):
		add(f[i], 1)
	M = m
	for i in range(m):
		ai = a[i] - 1
		mn[ai] = 1
		index = sum(f[ai])
		if mx[ai] < index:
			mx[ai] = index
		add(M, 1)
		add(f[ai], -1)
		f[ai] = M
		M -= 1
	for i in range(n):
		index = sum(f[i])
		if mx[i] < index:
			mx[i] = index
	for i in range(n):
		print(mn[i], mx[i])
	return
manager_simulator()


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 factorial
from collections import Counter, defaultdict, deque
from heapq import heapify, heappop, heappush

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

def comb(n, m):
	return factorial(n) / (factorial(m) * factorial(n - m)) if n >= m else 0

def perm(n, m):
	return factorial(n) // factorial(n - m) if n >= m else 0

def mdis(x1, y1, x2, y2):
	return abs(x1 - x2) + abs(y1 - y2)
mod = 998244353
INF = float('inf')

class BIT:

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

	def lowbit(self, num):
		return num & -num

	def update(self, ind, val):
		while ind < self.n + 1:
			self.btree[ind] += val
			ind += self.lowbit(ind)

	def sum(self, ind):
		res = 0
		while ind:
			res += self.btree[ind]
			ind -= self.lowbit(ind)
		return res

def main():
	(n, m) = RL()
	arr = RLL()
	bt = BIT(n + m)
	mi = [i for i in range(n + 1)]
	ma = [i for i in range(n + 1)]
	for i in range(1, n + 1):
		bt.update(m + i, 1)
	rec = [i + m for i in range(n + 1)]
	pos = m
	for q in arr:
		mi[q] = 1
		ma[q] = max(ma[q], bt.sum(rec[q]))
		bt.update(pos, 1)
		bt.update(rec[q], -1)
		rec[q] = pos
		pos -= 1
	for i in range(1, n + 1):
		ma[i] = max(ma[i], bt.sum(rec[i]))
	for i in range(1, n + 1):
		print(mi[i], ma[i])
main()


import sys
input = sys.stdin.readline
INF = 10 ** 9
(n, m) = [int(item) for item in input().split()]
a = [int(item) for item in input().split()]
maximum = [item for item in range(n)]
minimum = [item for item in range(n)]
place = dict()
for i in range(n):
	place[i] = i + m
length = m + n
bit = [0] * (m + 1) + [1] * n

def bit_init():
	for i in range(1, length):
		if i + (i & -i) > length:
			continue
		bit[i + (i & -i)] += bit[i]

def bit_add(x, w):
	x += 1
	while x <= length:
		bit[x] += w
		x += x & -x

def bit_sum(x):
	ret = 0
	while x > 0:
		ret += bit[x]
		x -= x & -x
	return ret
bit_init()
ptr = m - 1
for item in a:
	rank = bit_sum(place[item - 1])
	maximum[item - 1] = max(maximum[item - 1], rank)
	minimum[item - 1] = 0
	bit_add(place[item - 1], -1)
	place[item - 1] = ptr
	bit_add(place[item - 1], 1)
	ptr -= 1
for i in range(n):
	rank = bit_sum(place[i])
	maximum[i] = max(maximum[i], rank)
for (minn, maxx) in zip(minimum, maximum):
	print(minn + 1, maxx + 1)


import sys, math
import io, os
from collections import defaultdict as dd, deque, Counter

def data():
	return sys.stdin.buffer.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')
mod = int(1000000000.0) + 7

def update(v, w):
	while v <= N:
		BIT[v] += w
		v += v & -v

def getvalue(v):
	ANS = 0
	while v != 0:
		ANS += BIT[v]
		v -= v & -v
	return ANS

def bisect_on_BIT(x):
	if x <= 0:
		return 0
	ANS = 0
	h = 1 << n - 1
	while h > 0:
		if ANS + h <= n and BIT[ANS + h] < x:
			x -= BIT[ANS + h]
			ANS += h
		h //= 2
	return ANS + 1
(n, m) = mdata()
a = mdata()
BIT = [0] * (n + m + 1)
N = n + m
pos = [0] * (n + 1)
v = [0] * (n + 1)
for i in range(1, n + 1):
	pos[i] = n - i + 1
	v[i] = i
	update(i, 1)
for i in range(m):
	v[a[i]] = max(v[a[i]], getvalue(n + i) - getvalue(pos[a[i]]) + 1)
	update(pos[a[i]], -1)
	pos[a[i]] = n + i + 1
	update(pos[a[i]], 1)
s = set(a)
for i in range(1, n + 1):
	v[i] = max(v[i], getvalue(n + m) - getvalue(pos[i]) + 1)
	if i in s:
		print(1, v[i])
	else:
		print(i, v[i])


debug = 0
(n, m) = map(int, input().split())
a = list(map(int, input().split()))

class Node:

	def __init__(self, par, l, r, v, leaf=True, cl=None, cr=None) -> None:
		self.par = par
		self.l = l
		self.r = r
		self.v = v
		self.leaf = leaf
		self.cl = cl
		self.cr = cr
where = list(reversed(range(n)))

def mktree(par, l, r, n):
	node = Node(par, l, r, max(0, min(n, r) - l))
	if l + 1 < r:
		mid = (l + r) // 2
		(node.cl, node.cr) = (mktree(node, l, mid, n), mktree(node, mid, r, n))
		node.leaf = False
	return node

def pos(x, node, change=0):
	node.v += change
	if node.leaf:
		return node.v - change
	else:
		mid = (node.l + node.r) // 2
		if x >= mid:
			return node.cl.v + pos(x, node.cr, change)
		else:
			return pos(x, node.cl, change)
root = mktree(None, 0, n + m, n)
if debug:
	for i in range(n + m):
		print(i, '--', pos(i, root))
	print(root)
mx = list(range(n))
mn = list(range(n))
for i in range(m):
	aa = a[i] - 1
	v = pos(where[aa], root, -1)
	pos(i + n, root, 1)
	where[aa] = i + n
	mn[aa] = 0
	mx[aa] = max(mx[aa], n - v)
	if debug:
		print('aa,v,n-v-1', aa, v, n - v)
if debug:
	print(root)
if debug:
	print('where: ', where)
if debug:
	for i in range(n + m):
		print(i, '--', pos(i, root))
final = sorted(range(n), key=lambda x: where[x])
for (pos, i) in enumerate(final):
	mx[i] = max(mx[i], n - pos - 1)
for (x, y) in zip(mn, mx):
	print(x + 1, y + 1)


INF = 10 ** 10

def main():
	(n, m) = get_list()
	li = get_list()
	indexes = [[] for _ in range(n)]
	for (i, ele) in enumerate(li):
		indexes[ele - 1].append(i)
	stree1 = SegTreeSum(n)
	res = [[i + 1, -1] for i in range(n)]
	for j in range(m):
		i = li[j] - 1
		res[i][0] = 1
		if res[i][1] == -1:
			res[i][1] = stree1.query(i + 1, n - 1) + i + 1
		stree1.modify(i, 1)
	for i in range(n):
		if res[i][1] == -1:
			res[i][1] = stree1.query(i + 1, n - 1) + i + 1
	prev = dict()
	stree = SegTreeSum(m)
	for (i, ele) in enumerate(li):
		if ele in prev:
			stree.modify(prev[ele], 0)
			res[ele - 1][1] = max(res[ele - 1][1], 1 + stree.query(prev[ele], i))
		stree.modify(i, 1)
		prev[ele] = i
	for ele in range(n):
		if ele + 1 in prev:
			res[ele][1] = max(res[ele][1], 1 + stree.query(prev[ele + 1] + 1, m - 1))
	[print(' '.join(map(str, x))) for x in res]

class SegTreeSum:

	def __init__(self, size):
		self.n = 1 << size.bit_length()
		self.li = [0] * (self.n << 1)

	def modify(self, index, ele):
		index += self.n
		self.li[index] = ele
		while index > 1:
			self.li[index >> 1] = self.li[index] + self.li[index ^ 1]
			index >>= 1

	def get(self, index):
		return self.li[self.n + index]

	def debug(self):
		[print(i, self.li[i]) for i in range(len(self.li))]

	def query(self, l, r):
		res = 0
		(l, r) = (l + self.n, r + self.n)
		while l <= r:
			if l & 1 == 1:
				res += self.li[l]
			if r & 1 != 1:
				res += self.li[r]
			l = l + 1 >> 1
			r = r - 1 >> 1
		return res
import sys
from collections import defaultdict, Counter
from bisect import bisect_left, bisect_right
import math
input = iter(sys.stdin.buffer.read().decode().splitlines()).__next__
out = []
get_int = lambda : int(input())
get_list = lambda : list(map(int, input().split()))
main()
print(*out, sep='\n')


from collections import defaultdict
from bisect import bisect_left

def merge(l1, l2):
	v1 = v2 = 0
	(n1, n2) = (len(l1), len(l2))
	ret = []
	for _ in range(n1 + n2):
		f = 0
		if v1 == n1:
			f = 1
		elif v2 == n2:
			f = 0
		elif l1[v1] < l2[v2]:
			f = 0
		else:
			f = 1
		if f:
			ret.append(l2[v2])
			v2 += 1
		else:
			ret.append(l1[v1])
			v1 += 1
	return ret

class Segtree_With_Vectors:

	def __init__(self, n):
		self.n0 = 2 ** (n - 1).bit_length()
		self.data = [[] for i in range(2 * self.n0)]

	def construct(self, lis):
		for (i, x) in enumerate(lis):
			self.data[i + self.n0 - 1] = [x]
		for i in range(self.n0 - 2, -1, -1):
			self.data[i] = merge(self.data[2 * i + 1], self.data[2 * i + 2])

	def query(self, l, r, k):
		l += self.n0
		r += self.n0
		res = 0
		while l < r:
			if r & 1:
				r -= 1
				res += bisect_left(self.data[r - 1], k)
			if l & 1:
				res += bisect_left(self.data[l - 1], k)
				l += 1
			l >>= 1
			r >>= 1
		return res

class Binary_Indexed_Tree:

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

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

	def sum(self, i):
		ret = 0
		while i:
			ret += self.data[i]
			i &= i - 1
		return ret
(n, m) = map(int, input().split())
a = list(map(int, input().split()))
mi = [i for i in range(n)]
ma = [i for i in range(n)]
prev = []
d = defaultdict(lambda : -1)
history = defaultdict(list)
for (i, ai) in enumerate(a):
	history[ai].append(i)
	prev.append(d[ai])
	d[ai] = i
used = set()
BIT = Binary_Indexed_Tree(n)
for i in a:
	if i in used:
		continue
	mi[i - 1] = 0
	ma[i - 1] = i - 1 + BIT.sum(n - i + 1)
	BIT.add(n - i + 1, 1)
	used.add(i)
for i in range(1, n + 1):
	if i in used:
		continue
	ma[i - 1] = i - 1 + BIT.sum(n - i + 1)
Seg = Segtree_With_Vectors(m)
Seg.construct(prev)
for i in range(n):
	k = len(history[i + 1])
	for j in range(k):
		l = history[i + 1][j]
		if j == k - 1:
			r = m
		else:
			r = history[i + 1][j + 1]
		tmp = Seg.query(l + 1, r, l + 1)
		ma[i] = max(ma[i], tmp)
for (i, j) in zip(mi, ma):
	print(i + 1, j + 1)


import sys, os, io
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, m) = [int(i) for i in input().split()]
a = [int(i) - 1 for i in input().split()]
mini = [i for i in range(1, n + 1)]
maxi = [i for i in range(1, n + 1)]
for i in a:
	mini[i] = 1
s = SortedList()
curr = 100000
for i in range(n):
	s.add((curr, i))
prev = [100000] * n
for i in a:
	ele = (prev[i], i)
	ind = s.bisect_left(ele)
	maxi[i] = max(maxi[i], ind + 1)
	s.remove(ele)
	curr -= 1
	s.add((curr, i))
	prev[i] = curr
for i in range(n):
	curr = s[i][1]
	maxi[curr] = max(maxi[curr], i + 1)
maxi[s[-1][1]] = n
for i in range(n):
	print(mini[i], maxi[i])


import io
import os
import random

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

	def __init__(self, data=None):
		if data:
			data = sorted(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)

	def __getitem__(self, index):
		return treap_find_kth(self.root, index)

	def bisect_left(self, value):
		return treap_bisect_left(self.root, value)

	def bisect_right(self, value):
		return treap_bisect_right(self.root, value)

class TreapSet(TreapMultiSet):

	def add(self, key):
		(self.root, duplicate) = treap_insert_unique(self.root, key)
		if not duplicate:
			self.size += 1

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

class TreapHashSet(TreapMultiSet):

	def __init__(self, data=None):
		if data:
			self.keys = set(data)
			super(TreapHashSet, self).__init__(self.keys)
		else:
			self.keys = set()

	def add(self, key):
		if key not in self.keys:
			self.keys.add(key)
			super(TreapHashSet, self).add(key)

	def remove(self, key):
		self.keys.remove(key)
		super(TreapHashSet, self).remove(key)

	def discard(self, key):
		if key in self.keys:
			self.remove(key)

	def __contains__(self, key):
		return key in self.keys

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

class TreapHashMap(TreapMultiSet):

	def __init__(self, data=None):
		if data:
			self.map = dict(data)
			super(TreapHashMap, self).__init__(self.map.keys())
		else:
			self.map = dict()

	def __setitem__(self, key, value):
		if key not in self.map:
			super(TreapHashMap, self).add(key)
		self.map[key] = value

	def __getitem__(self, key):
		return self.map[key]

	def add(self, key):
		raise TypeError('add on TreapHashMap')

	def get(self, key, default=None):
		return self.map.get(key, default=default)

	def remove(self, key):
		self.map.pop(key)
		super(TreapHashMap, self).remove(key)

	def discard(self, key):
		if key in self.map:
			self.remove(key)

	def __contains__(self, key):
		return key in self.map

	def __repr__(self):
		return 'TreapHashMap({})'.format(list(self))
left_child = [0]
right_child = [0]
subtree_size = [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)
		subtree_size[root] = end - begin
		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)
	subtree_size.append(1)
	return len(treap_keys) - 1

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

def treap_merge(left, right):
	(where, pos) = (left_child, 0)
	stack = []
	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]
		stack.append(pos)
	where[pos] = left or right
	node = left_child[0]
	left_child[0] = 0
	treap_update(stack)
	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
	stack = [root]
	while root and treap_keys[root] != key:
		parent = root
		root = left_child[root] if key < treap_keys[root] else right_child[root]
		stack.append(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])
	treap_update(stack)
	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

def treap_update(path):
	for node in reversed(path):
		assert node != 0
		lc = left_child[node]
		rc = right_child[node]
		subtree_size[node] = subtree_size[lc] + 1 + subtree_size[rc]

def treap_find_kth(root, k):
	if not root or not 0 <= k < subtree_size[root]:
		raise IndexError('treap index out of range')
	while True:
		lc = left_child[root]
		left_size = subtree_size[lc]
		if k < left_size:
			root = lc
			continue
		k -= left_size
		if k == 0:
			return treap_keys[root]
		k -= 1
		rc = right_child[root]
		root = rc

def treap_bisect_left(root, key):
	index = 0
	while root:
		if treap_keys[root] < key:
			index += subtree_size[left_child[root]] + 1
			root = right_child[root]
		else:
			root = left_child[root]
	return index

def treap_bisect_right(root, key):
	index = 0
	while root:
		if treap_keys[root] <= key:
			index += subtree_size[left_child[root]] + 1
			root = right_child[root]
		else:
			root = left_child[root]
	return index

def solve(N, M, messages):
	ans = [[i, i] for i in range(N)]
	friendsList = TreapMultiSet()
	friendsToTime = {i: i for i in range(N)}
	for (f, t) in friendsToTime.items():
		friendsList.add((t, f))
	for (t, f) in enumerate(messages):
		index = friendsList.bisect_left((friendsToTime[f], f))
		ans[f][1] = max(ans[f][1], index)
		friendsList.remove((friendsToTime[f], f))
		friendsToTime[f] = -t - 1
		friendsList.add((friendsToTime[f], f))
		ans[f][0] = min(ans[f][0], 0)
	for (i, (t, f)) in enumerate(friendsList):
		ans[f][0] = min(ans[f][0], i)
		ans[f][1] = max(ans[f][1], i)
	return '\n'.join((str(x + 1) + ' ' + str(y + 1) for (x, y) in ans))
input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline
(N, M) = [int(x) for x in input().split()]
messages = [int(x) - 1 for x in input().split()]
ans = solve(N, M, messages)
print(ans)


import sys
reader = (s.rstrip() for s in sys.stdin)
input = reader.__next__

class Binary_Indexed_Tree:

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

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

	def sum(self, i):
		i += 1
		ret = 0
		while i:
			ret += self.data[i]
			i &= i - 1
		return ret
(n, m) = map(int, input().split())
a = list(map(int, input().split()))
BIT = Binary_Indexed_Tree(n + m)
pos = [n - 1 - i for i in range(n)]
for i in range(n):
	BIT.add(i, 1)
min_ = [i for i in range(n)]
max_ = [i for i in range(n)]
for i in range(m):
	ai = a[i] - 1
	tmp = n - BIT.sum(pos[ai])
	max_[ai] = max(max_[ai], tmp)
	BIT.add(pos[ai], -1)
	pos[ai] = n + i
	BIT.add(pos[ai], 1)
	min_[ai] = 0
for i in range(n):
	tmp = n - BIT.sum(pos[i])
	max_[i] = max(max_[i], tmp)
for (mi, ma) in zip(min_, max_):
	print(mi + 1, ma + 1)


import sys
input = sys.stdin.readline
(n, m) = map(int, input().split())
A = list(map(int, input().split()))
LEN = n + m
BIT = [0] * (LEN + 1)

def update(v, w):
	while v <= LEN:
		BIT[v] += w
		v += v & -v

def getvalue(v):
	ANS = 0
	while v != 0:
		ANS += BIT[v]
		v -= v & -v
	return ANS
NOW = [i + m for i in range(n + 1)]
for i in range(1, n + 1):
	update(m + i, 1)
AMIN = [i for i in range(n + 1)]
AMAX = [i for i in range(n + 1)]
F = m
for a in A:
	AMAX[a] = max(AMAX[a], getvalue(NOW[a]))
	AMIN[a] = 1
	update(NOW[a], -1)
	update(F, 1)
	NOW[a] = F
	F -= 1
for i in range(1, n + 1):
	AMAX[i] = max(AMAX[i], getvalue(NOW[i]))
for i in range(1, n + 1):
	print(AMIN[i], AMAX[i])


from sys import stdin, stdout

def update(bita, pos, v):
	while pos < len(bita):
		bita[pos] += v
		pos += lowbit(pos)

def query(bita, pos):
	res = 0
	while pos > 0:
		res += bita[pos]
		pos -= lowbit(pos)
	return res

def lowbit(p):
	return p & -p

def getminmax(n, m, ma):
	bita = [0] * (n + m + 1)
	minmax = [[0, 0] for i in range(n + 1)]
	pos = [0] * (n + 1)
	for i in range(1, n + 1):
		update(bita, n + 1 - i, 1)
		minmax[i][0] = i
		minmax[i][1] = i
		pos[i] = n + 1 - i
	for i in range(n + 1, n + 1 + m):
		mes = ma[i - n - 1]
		minmax[mes][0] = 1
		minmax[mes][1] = max(minmax[mes][1], n - query(bita, pos[mes] - 1))
		update(bita, pos[mes], -1)
		pos[mes] = i
		update(bita, pos[mes], 1)
	for i in range(1, n + 1):
		minmax[i][1] = max(minmax[i][1], n - query(bita, pos[i] - 1))
	return minmax
nm = list(map(int, stdin.readline().split()))
n = nm[0]
m = nm[1]
ma = list(map(int, stdin.readline().split()))
minmax = getminmax(n, m, ma)
for i in range(1, n + 1):
	stdout.write(str(minmax[i][0]) + ' ' + str(minmax[i][1]) + '\n')


import math
import random
import heapq, bisect
import sys
from collections import deque, defaultdict
from fractions import Fraction
import sys
import threading
from collections import defaultdict
mod = 10 ** 9 + 7
mod1 = 998244353
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')

class TreeNode:

	def __init__(self, k, v):
		self.key = k
		self.value = v
		self.left = None
		self.right = None
		self.parent = None
		self.height = 1
		self.num_left = 1
		self.num_total = 1

class AvlTree:

	def __init__(self):
		self._tree = None

	def add(self, k, v):
		if not self._tree:
			self._tree = TreeNode(k, v)
			return
		node = self._add(k, v)
		if node:
			self._rebalance(node)

	def _add(self, k, v):
		node = self._tree
		while node:
			if k < node.key:
				if node.left:
					node = node.left
				else:
					node.left = TreeNode(k, v)
					node.left.parent = node
					return node.left
			elif node.key < k:
				if node.right:
					node = node.right
				else:
					node.right = TreeNode(k, v)
					node.right.parent = node
					return node.right
			else:
				node.value = v
				return

	@staticmethod
	def get_height(x):
		return x.height if x else 0

	@staticmethod
	def get_num_total(x):
		return x.num_total if x else 0

	def _rebalance(self, node):
		n = node
		while n:
			lh = self.get_height(n.left)
			rh = self.get_height(n.right)
			n.height = max(lh, rh) + 1
			balance_factor = lh - rh
			n.num_total = 1 + self.get_num_total(n.left) + self.get_num_total(n.right)
			n.num_left = 1 + self.get_num_total(n.left)
			if balance_factor > 1:
				if self.get_height(n.left.left) < self.get_height(n.left.right):
					self._rotate_left(n.left)
				self._rotate_right(n)
			elif balance_factor < -1:
				if self.get_height(n.right.right) < self.get_height(n.right.left):
					self._rotate_right(n.right)
				self._rotate_left(n)
			else:
				n = n.parent

	def _remove_one(self, node):
		replacement = node.left or node.right
		if node.parent:
			if AvlTree._is_left(node):
				node.parent.left = replacement
			else:
				node.parent.right = replacement
			replacement.parent = node.parent
			node.parent = None
		else:
			self._tree = replacement
			replacement.parent = None
		node.left = None
		node.right = None
		node.parent = None
		self._rebalance(replacement)

	def _remove_leaf(self, node):
		if node.parent:
			if AvlTree._is_left(node):
				node.parent.left = None
			else:
				node.parent.right = None
			self._rebalance(node.parent)
		else:
			self._tree = None
		node.parent = None
		node.left = None
		node.right = None

	def remove(self, k):
		node = self._get_node(k)
		if not node:
			return
		if AvlTree._is_leaf(node):
			self._remove_leaf(node)
			return
		if node.left and node.right:
			nxt = AvlTree._get_next(node)
			node.key = nxt.key
			node.value = nxt.value
			if self._is_leaf(nxt):
				self._remove_leaf(nxt)
			else:
				self._remove_one(nxt)
			self._rebalance(node)
		else:
			self._remove_one(node)

	def get(self, k):
		node = self._get_node(k)
		return node.value if node else -1

	def _get_node(self, k):
		if not self._tree:
			return None
		node = self._tree
		while node:
			if k < node.key:
				node = node.left
			elif node.key < k:
				node = node.right
			else:
				return node
		return None

	def get_at(self, pos):
		x = pos + 1
		node = self._tree
		while node:
			if x < node.num_left:
				node = node.left
			elif node.num_left < x:
				x -= node.num_left
				node = node.right
			else:
				return (node.key, node.value)
		raise IndexError('Out of ranges')

	@staticmethod
	def _is_left(node):
		return node.parent.left and node.parent.left == node

	@staticmethod
	def _is_leaf(node):
		return node.left is None and node.right is None

	def _rotate_right(self, node):
		if not node.parent:
			self._tree = node.left
			node.left.parent = None
		elif AvlTree._is_left(node):
			node.parent.left = node.left
			node.left.parent = node.parent
		else:
			node.parent.right = node.left
			node.left.parent = node.parent
		bk = node.left.right
		node.left.right = node
		node.parent = node.left
		node.left = bk
		if bk:
			bk.parent = node
		node.height = max(self.get_height(node.left), self.get_height(node.right)) + 1
		node.num_total = 1 + self.get_num_total(node.left) + self.get_num_total(node.right)
		node.num_left = 1 + self.get_num_total(node.left)

	def _rotate_left(self, node):
		if not node.parent:
			self._tree = node.right
			node.right.parent = None
		elif AvlTree._is_left(node):
			node.parent.left = node.right
			node.right.parent = node.parent
		else:
			node.parent.right = node.right
			node.right.parent = node.parent
		bk = node.right.left
		node.right.left = node
		node.parent = node.right
		node.right = bk
		if bk:
			bk.parent = node
		node.height = max(self.get_height(node.left), self.get_height(node.right)) + 1
		node.num_total = 1 + self.get_num_total(node.left) + self.get_num_total(node.right)
		node.num_left = 1 + self.get_num_total(node.left)

	@staticmethod
	def _get_next(node):
		if not node.right:
			return node.parent
		n = node.right
		while n.left:
			n = n.left
		return n

class SegmentTree1:

	def __init__(self, data, default=2 ** 30, func=lambda a, b: min(a, b)):
		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):
		if start == stop:
			return self.__getitem__(start)
		stop += 1
		start += self._size
		stop += self._size
		res = self._default
		while start < stop:
			if start & 1:
				res = self._func(res, self.data[start])
				start += 1
			if stop & 1:
				stop -= 1
				res = self._func(res, self.data[stop])
			start >>= 1
			stop >>= 1
		return res

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

class SegmentTree:

	def __init__(self, data, default=0, func=lambda a, b: a + b):
		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):
		if start == stop:
			return self.__getitem__(start)
		stop += 1
		start += self._size
		stop += self._size
		res = self._default
		while start < stop:
			if start & 1:
				res = self._func(res, self.data[start])
				start += 1
			if stop & 1:
				stop -= 1
				res = self._func(res, self.data[stop])
			start >>= 1
			stop >>= 1
		return res

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

class Factorial:

	def __init__(self, MOD):
		self.MOD = MOD
		self.factorials = [1, 1]
		self.invModulos = [0, 1]
		self.invFactorial_ = [1, 1]

	def calc(self, n):
		if n <= -1:
			print('Invalid argument to calculate n!')
			print('n must be non-negative value. But the argument was ' + str(n))
			exit()
		if n < len(self.factorials):
			return self.factorials[n]
		nextArr = [0] * (n + 1 - len(self.factorials))
		initialI = len(self.factorials)
		prev = self.factorials[-1]
		m = self.MOD
		for i in range(initialI, n + 1):
			prev = nextArr[i - initialI] = prev * i % m
		self.factorials += nextArr
		return self.factorials[n]

	def inv(self, n):
		if n <= -1:
			print('Invalid argument to calculate n^(-1)')
			print('n must be non-negative value. But the argument was ' + str(n))
			exit()
		p = self.MOD
		pi = n % p
		if pi < len(self.invModulos):
			return self.invModulos[pi]
		nextArr = [0] * (n + 1 - len(self.invModulos))
		initialI = len(self.invModulos)
		for i in range(initialI, min(p, n + 1)):
			next = -self.invModulos[p % i] * (p // i) % p
			self.invModulos.append(next)
		return self.invModulos[pi]

	def invFactorial(self, n):
		if n <= -1:
			print('Invalid argument to calculate (n^(-1))!')
			print('n must be non-negative value. But the argument was ' + str(n))
			exit()
		if n < len(self.invFactorial_):
			return self.invFactorial_[n]
		self.inv(n)
		nextArr = [0] * (n + 1 - len(self.invFactorial_))
		initialI = len(self.invFactorial_)
		prev = self.invFactorial_[-1]
		p = self.MOD
		for i in range(initialI, n + 1):
			prev = nextArr[i - initialI] = prev * self.invModulos[i % p] % p
		self.invFactorial_ += nextArr
		return self.invFactorial_[n]

class Combination:

	def __init__(self, MOD):
		self.MOD = MOD
		self.factorial = Factorial(MOD)

	def ncr(self, n, k):
		if k < 0 or n < k:
			return 0
		k = min(k, n - k)
		f = self.factorial
		return f.calc(n) * f.invFactorial(max(n - k, k)) * f.invFactorial(min(k, n - k)) % self.MOD

def powm(a, n, m):
	if a == 1 or n == 0:
		return 1
	if n % 2 == 0:
		s = powm(a, n // 2, m)
		return s * s % m
	else:
		return a * powm(a, n - 1, m) % m

def sort_list(list1, list2):
	zipped_pairs = zip(list2, list1)
	z = [x for (_, x) in sorted(zipped_pairs)]
	return z

def product(l):
	por = 1
	for i in range(len(l)):
		por *= l[i]
	return por

def binarySearchCount(arr, n, key):
	left = 0
	right = n - 1
	count = 0
	while left <= right:
		mid = int((right + left) / 2)
		if arr[mid] < key:
			count = mid + 1
			left = mid + 1
		else:
			right = mid - 1
	return count

def countdig(n):
	c = 0
	while n > 0:
		n //= 10
		c += 1
	return c

def binary(x, length):
	y = bin(x)[2:]
	return y if len(y) >= length else '0' * (length - len(y)) + y

def countGreater(arr, n, k):
	l = 0
	r = n - 1
	leftGreater = n
	while l <= r:
		m = int(l + (r - l) / 2)
		if arr[m] > k:
			leftGreater = m
			r = m - 1
		else:
			l = m + 1
	return n - leftGreater

class TrieNode:

	def __init__(self):
		self.children = [None] * 26
		self.isEndOfWord = False

class Trie:

	def __init__(self):
		self.root = self.getNode()

	def getNode(self):
		return TrieNode()

	def _charToIndex(self, ch):
		return ord(ch) - ord('a')

	def insert(self, key):
		pCrawl = self.root
		length = len(key)
		for level in range(length):
			index = self._charToIndex(key[level])
			if not pCrawl.children[index]:
				pCrawl.children[index] = self.getNode()
			pCrawl = pCrawl.children[index]
		pCrawl.isEndOfWord = True

	def search(self, key):
		pCrawl = self.root
		length = len(key)
		for level in range(length):
			index = self._charToIndex(key[level])
			if not pCrawl.children[index]:
				return False
			pCrawl = pCrawl.children[index]
		return pCrawl != None and pCrawl.isEndOfWord

class Node:

	def __init__(self, data):
		self.data = data
		self.count = 0
		self.left = None
		self.right = None

class BinaryTrie:

	def __init__(self):
		self.root = Node(0)

	def insert(self, pre_xor):
		self.temp = self.root
		for i in range(31, -1, -1):
			val = pre_xor & 1 << i
			if val:
				if not self.temp.right:
					self.temp.right = Node(0)
				self.temp = self.temp.right
				self.temp.count += 1
			if not val:
				if not self.temp.left:
					self.temp.left = Node(0)
				self.temp = self.temp.left
				self.temp.count += 1
		self.temp.data = pre_xor

	def query(self, xor):
		self.temp = self.root
		for i in range(31, -1, -1):
			val = xor & 1 << i
			if not val:
				if self.temp.left and self.temp.left.count > 0:
					self.temp = self.temp.left
				elif self.temp.right:
					self.temp = self.temp.right
			elif self.temp.right and self.temp.right.count > 0:
				self.temp = self.temp.right
			elif self.temp.left:
				self.temp = self.temp.left
			self.temp.count -= 1
		return xor ^ self.temp.data
(n, m) = map(int, input().split())
l = list(map(int, input().split()))
se = set(l)
mi = [0] * (n + 1)
ma = [0] * (n + 1)
pos = [i + m - 1 for i in range(n + 1)]
for i in range(1, n + 1):
	if i in se:
		mi[i] = 1
	else:
		mi[i] = i
a = [0] * m + [1 for i in range(1, n + 1)] + []
t = m - 1
s = SegmentTree(a)
for i in range(m):
	w = l[i]
	ma[l[i]] = max(ma[l[i]], s.query(0, pos[l[i]]))
	last = pos[l[i]]
	pos[l[i]] = t
	t -= 1
	s.__setitem__(t + 1, 1)
	s.__setitem__(last, 0)
	a[t + 1] = 1
	a[last] = 0
for i in range(1, n + 1):
	ma[i] = max(ma[i], s.query(0, pos[i]))
	print(mi[i], ma[i])


import sys
input = sys.stdin.readline
from collections import defaultdict

class Bit:

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

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

	def add(self, i, x):
		while i <= self.size:
			self.tree[i] += x
			i += i & -i
(n, m) = map(int, input().split())
ipt = list(map(int, input().split()))
a = [i for i in range(n, 0, -1)] + ipt
rng = []
dc = defaultdict(int)
for i in range(n + m):
	x = a[i]
	rng.append((dc[x], i + 1))
	dc[x] = i + 1
rng.sort(key=lambda x: x[1])
bit = Bit(n + m + 1)
ansmx = [0 for i in range(n + 1)]
for (l, r) in rng:
	bit.add(l + 1, 1)
	bit.add(r, -1)
	if l == 0:
		x = a[r - 1]
	else:
		x = a[l - 1]
	ansmx[x] = max(ansmx[x], bit.sum(l))
for i in range(1, n + 1):
	ansmx[i] = max(ansmx[i], bit.sum(dc[i]))
setipt = set(ipt)
for i in range(1, n + 1):
	if i in setipt:
		mn = 1
	else:
		mn = i
	print(mn, ansmx[i] + 1)


from __future__ import division, print_function
from fractions import Fraction
import sys
import os
from io import BytesIO, IOBase
from functools import cmp_to_key
from heapq import *
from math import gcd, factorial, floor, ceil
from copy import deepcopy
from collections import deque
from bisect import bisect_left as bl
from bisect import bisect_right as br
from bisect import bisect
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

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
inf = pow(10, 20)
mod = 998244353

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

	def printpref(self):
		out = []
		for i in range(len(self.bit) + 1):
			out.append(self.query(i))
		print(out)

def solve(case):
	(n, m) = sep()
	a = lis()
	for i in range(m):
		a[i] -= 1
	temp = [1 for i in range(n)]
	for i in range(m):
		temp.append(0)
	f = FenwickTree(temp)
	mn = [i for i in range(0, n)]
	for i in range(m):
		mn[a[i]] = 0
	mx = [i for i in range(n)]
	pos = [n - i - 1 for i in range(n)]
	for i in range(m):
		mx[a[i]] = max(mx[a[i]], n - f.query(pos[a[i]] + 1))
		f.update(pos[a[i]], -1)
		pos[a[i]] = i + n
		f.update(pos[a[i]], 1)
	for i in range(n):
		mx[i] = max(mx[i], n - f.query(pos[i] + 1))
	for i in range(n):
		print(mn[i] + 1, mx[i] + 1)
testcase(1)


import io
import os

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(N, M, messages):
	ans = [[i, i] for i in range(N)]
	friendsList = SortedList()
	friendsToTime = {i: i for i in range(N)}
	for (f, t) in friendsToTime.items():
		friendsList.add((t, f))
	for (t, f) in enumerate(messages):
		index = friendsList.bisect_left((friendsToTime[f], f))
		ans[f][1] = max(ans[f][1], index)
		friendsList.remove((friendsToTime[f], f))
		friendsToTime[f] = -t - 1
		friendsList.add((friendsToTime[f], f))
		ans[f][0] = min(ans[f][0], 0)
	for (i, (t, f)) in enumerate(friendsList):
		ans[f][0] = min(ans[f][0], i)
		ans[f][1] = max(ans[f][1], i)
	return '\n'.join((str(x + 1) + ' ' + str(y + 1) for (x, y) in ans))
input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline
(N, M) = [int(x) for x in input().split()]
messages = [int(x) - 1 for x in input().split()]
ans = solve(N, M, messages)
print(ans)