There are N hidden integer arrays of length N each. You are given the mex of each of these N arrays.

Ashish likes lower bounds and Kryptonix likes upper bounds. So, for each 0 ≤ i ≤ N-1, find:
The least possible number of occurrences of i across all the arrays
The most possible number of occurrences of i across all the arrays

Note that these values must be computed independently, i.e, it is allowed to choose different configurations of arrays to attempt to minimize/maximize the number of occurrences of different integers.

Please see the samples for an example.

Recall that the mex of an array is the smallest non-negative integer that is not present in it. For example, the mex of [0, 2, 4, 1, 1, 5] is 3, and the mex of [3, 8, 101, 99, 100] is 0.

------ Input Format ------ 

- The first line of input contains a single integer T — the number of test cases. Then the test cases follow.
- The first line of each test case contains an integer N — the size of the array.
- The second line of each test case contains N space-separated integers A_{1}, A_{2}, \dots, A_{N}, denoting the mexes of the N arrays.

------ Output Format ------ 

For each test case, output N lines, each containing two space-separated integers. The i-th line should contain the least and the most possible number of occurrences of i across all the arrays.

------ Constraints ------ 

$1 ≤ T ≤ 10^{4}$
$1 ≤ N ≤ 3\cdot10^{5}$
$0 ≤ A_{i} ≤ N$
- The sum of $N$ over all test cases does not exceed $3\cdot10^{5}$

----- Sample Input 1 ------ 
3
2
1 0
5
3 1 5 0 2
3
1 2 1
----- Sample Output 1 ------ 
1 2
0 2
4 13
3 13
2 13
1 13
1 15
3 8
1 2
0 4
----- explanation 1 ------ 
Test case $1$: We have the following:
- For $i = 0$, the two arrays can be $[0, 3]$ and $[2, 4]$ giving us one zero, or $[0, 0]$ and $[3, 1]$ giving us $2$ zeros.
- For $i = 1$, $[0, 4]$ and $[3, 4]$ give no ones, while $[0, 9]$ and $[1, 1]$ give $2$ ones.

Test case $3$: We have the following:
- For $i = 0$, the arrays $[0, 3, 2], [1, 0, 4], [5, 0, 2]$ give the least number of zeros (i.e, $3$), and the arrays $[0, 0, 0], [1, 0, 0], [0, 0, 0]$ give the most.
- For $i = 1$, the arrays $[5, 7, 0], [0, 3, 1], [6, 0, 3]$ give the least number of ones and the arrays $[0, 3, 2], [1, 1, 0], [5, 0, 2]$ give the most.
- For $i = 2$, the arrays $[3, 0, 9], [0, 0, 1], [0, 0, 0]$ give the least number of twos and the arrays $[2, 0, 2], [0, 1, 0], [2, 2, 0]$ give the most.

Difficulty: MEDIUM_HARD
Tags: Sorting

Mathematics

Complete search
Skill types: Sorting

Complete search

Starter code:

Solutions:
t = int(input())
for a in range(t):
	n = int(input())
	l = list(map(int, input().split()))
	s = [0] * n
	p = [n ** 2 - sum(l)] * n
	for i in range(n):
		if l[i] < n:
			s[l[i]] += 1
			p[l[i]] -= n - l[i]
	for i in range(n):
		max = p[i]
		min = s[i]
		if i < n - 1:
			s[i + 1] += s[i]
		max += n - min
		print(n - min, max)


t = int(input())
while t:
	k = int(input())
	j = 0
	l = list(map(int, input().split()))
	(m, p, q) = ([0] * (k + 1), [0] * (k + 1), [0] * (k + 1))
	while j < k:
		m[0] = m[0] + 1
		m[l[j]] = m[l[j]] - 1
		p[0] = p[0] + (k - l[j] + 1)
		p[l[j]] = p[l[j]] - (k - l[j] + 1)
		q[k - 1] = q[k - 1] + (k - l[j])
		q[l[j]] = q[l[j]] - (k - l[j])
		j += 1
	s = 1
	while s < k:
		(p[s], m[s]) = (p[s] + p[s - 1], m[s] + m[s - 1])
		s += 1
	v = k - 1
	while v >= 0:
		q[v] = q[v] + q[v + 1]
		v -= 1
	a = 0
	while a < k:
		print(m[a], p[a] + q[a])
		a += 1
	t -= 1


def update(d, l, r, x):
	d[l] += x
	d[r + 1] -= x
for i in range(int(input())):
	n = int(input())
	a = [int(x) for x in input().split()]
	mn = [0 for i in range(n + 1)]
	mx = [0 for i in range(n + 1)]
	for i in a:
		if i != 0:
			update(mn, 0, i - 1, 1)
			update(mx, 0, i - 1, n - (i - 1))
		if i != n:
			update(mx, i + 1, n - 1, n - i)
	for i in range(1, n + 1):
		mx[i] += mx[i - 1]
		mn[i] += mn[i - 1]
	for i in range(n):
		print(mn[i], end=' ')
		print(mx[i])


T = int(input())
for _ in range(T):
	N = int(input())
	maxrarr = [0 for i in range(N + 1)]
	flag = 0
	call = 1
	bool = True
	arr = list(map(int, input().split()))
	maxlarr = [0 for i in range(N + 1)]
	minarr = [0 for i in range(N + 1)]
	for i in range(N):
		minarr[0] += 1
		minarr[arr[i]] -= 1
		call += 2
		maxlarr[0] += N - arr[i] + 1
		maxlarr[arr[i]] -= N - arr[i] + 1
		flag = 2
		bool = False
		maxrarr[N - 1] += N - arr[i]
		maxrarr[arr[i]] -= N - arr[i]
	for i in range(1, N + 1):
		minarr[i] += minarr[i - 1]
		call = 0
		maxlarr[i] += maxlarr[i - 1]
	for i in range(N - 1, -1, -1):
		maxrarr[i] += maxrarr[i + 1]
	bool = True
	call = 6
	flag += 1
	ans = ''
	for i in range(N):
		ans = maxlarr[i] + maxrarr[i]
		print(str(minarr[i]) + ' ' + str(ans))


from collections import defaultdict
from bisect import bisect_right
for _ in range(int(input())):
	dct = defaultdict(int)
	n = int(input())
	arr = list(map(int, input().split()))
	miny = [0 for i in range(n)]
	maxy = [0 for i in range(n)]
	total = 0
	tup = sorted(arr)
	for i in range(n):
		num = bisect_right(tup, i)
		if num < n and tup[num] == i:
			num += 1
		miny[i] = n - num
	for j in range(n):
		total += n - arr[j]
		dct[arr[j]] += n - arr[j]
	for i in range(n):
		maxy[i] = miny[i] + total - dct[i]
		print(miny[i], maxy[i])


for i in range(int(input())):
	n = int(input())
	A = [int(k) for k in input().split()]
	a = [0] * (n + 1)
	b1 = [0] * (n + 1)
	b2 = [0] * (n + 1)
	for k in range(n):
		a[0] += 1
		a[A[k]] -= 1
		b1[0] += n - A[k] + 1
		b1[A[k]] -= n - A[k] + 1
		b2[n - 1] += n - A[k]
		b2[A[k]] -= n - A[k]
	for k in range(1, n + 1):
		a[k] += a[k - 1]
		b1[k] += b1[k - 1]
	for k in range(n - 1, -1, -1):
		b2[k] += b2[k + 1]
	for k in range(n):
		print(a[k], b1[k] + b2[k])


for _ in range(int(input())):
	n = int(input())
	s = [int(x) for x in input().split()]
	mi = [0 for i in range(n + 2)]
	ma = [0 for i in range(n + 2)]
	for i in range(n):
		mi[0] += 1
		mi[s[i]] -= 1
		ma[0] += n - s[i] + 1
		ma[s[i]] -= n - s[i] + 1
		ma[s[i] + 1] += n - s[i]
	for i in range(1, n):
		mi[i] += mi[i - 1]
		ma[i] += ma[i - 1]
	for i in range(n):
		print(*[mi[i], ma[i]])


from bisect import bisect_right as br
for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	a.sort()
	mp = {}
	for v in a:
		if v in mp:
			mp[v] += 1
		else:
			mp[v] = 1
	for i in range(n + 1):
		if i not in mp:
			mp[i] = 0
	pref = [0] * (n + 1)
	pref[0] = n * mp[0]
	for i in range(1, n):
		pref[i] = pref[i - 1] + (n - i) * mp[i]
	suff = [0] * n
	suff[n - 1] = mp[n]
	for i in range(n - 2, -1, -1):
		suff[i] = suff[i + 1] + (n - i) * mp[i + 1]
	for i in range(n):
		mini = n - br(a, i)
		maxi = pref[i - 1] + suff[i]
		print(mini, maxi)


for _ in range(int(input())):
	n = int(input())
	x = [int(x) for x in input().split()]
	mn = [0] * (n + 1)
	mx = [0] * (n + 1)
	mr = [0] * (n + 1)
	for i in range(n):
		mn[0] += 1
		mn[x[i]] -= 1
		mx[0] += n - x[i] + 1
		mx[x[i]] -= n - x[i] + 1
		mr[n - 1] += n - x[i]
		mr[x[i]] -= n - x[i]
	for i in range(n):
		mn[i + 1] += mn[i]
		mx[i + 1] += mx[i]
	for i in range(n - 1, -1, -1):
		mr[i] += mr[i + 1]
	for i in range(n):
		print(mn[i], end=' ')
		print(mx[i] + mr[i])


n = int(input())
for w in range(n):
	n = int(input())
	li = list(map(int, input().split(' ')))
	minn = [0 for i in range(n + 1)]
	maxx = [0 for i in range(n + 1)]
	maxxr = [0 for i in range(n + 1)]
	for i in range(n):
		minn[0] += 1
		minn[li[i]] -= 1
		maxx[0] += n - li[i] + 1
		maxx[li[i]] -= n - li[i] + 1
		maxxr[n - 1] += n - li[i]
		maxxr[li[i]] -= n - li[i]
	for i in range(1, n):
		minn[i] += minn[i - 1]
		maxx[i] += maxx[i - 1]
	for i in reversed(range(n)):
		maxxr[i] += maxxr[i + 1]
	for i in range(n):
		xx = maxx[i] + maxxr[i]
		print(minn[i], xx)


for t in range(int(input())):
	n = int(input())
	minn = [0] * (n + 1)
	maxl = [0] * (n + 1)
	maxr = [0] * (n + 1)
	x1 = map(int, input().split())
	for x in x1:
		minn[0] += 1
		minn[x] -= 1
		maxl[0] += n - x + 1
		maxl[x] -= n - x + 1
		maxr[n - 1] += n - x
		maxr[x] -= n - x
	for i in range(1, n + 1):
		minn[i] += minn[i - 1]
		maxl[i] += maxl[i - 1]
	for i in range(n - 1, -1, -1):
		maxr[i] += maxr[i + 1]
	for i in range(0, n):
		temp = maxl[i] + maxr[i]
		print(minn[i], temp)


t = int(input())
for _ in range(t):
	n = int(input())
	arr = [int(i) for i in input().split()]
	(mini, maxl, maxr) = ([0] * (n + 1), [0] * (n + 1), [0] * (n + 1))
	for i in range(n):
		k = arr[i]
		mini[0] += 1
		mini[k] -= 1
		maxl[0] += n - k + 1
		maxl[k] -= n - k + 1
		maxr[n - 1] += n - k
		maxr[k] -= n - k
	for i in range(1, n + 1):
		mini[i] += mini[i - 1]
		maxl[i] += maxl[i - 1]
	for i in range(n - 1, -1, -1):
		maxr[i] += maxr[i + 1]
	for i in range(n):
		print(mini[i], maxl[i] + maxr[i])


for _ in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	minn = [0] * (n + 1)
	maxl = [0] * (n + 1)
	maxr = [0] * (n + 1)
	for i in range(n):
		x = l[i]
		minn[0] += 1
		minn[x] -= 1
		maxl[0] += n - x + 1
		maxl[x] -= n - x + 1
		maxr[n - 1] += n - x
		maxr[x] -= n - x
	for i in range(1, n + 1):
		minn[i] += minn[i - 1]
		maxl[i] += maxl[i - 1]
	for i in range(n - 1, -1, -1):
		maxr[i] += maxr[i + 1]
	for i in range(n):
		print(minn[i], maxr[i] + maxl[i])


t = int(input())
for _ in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	vals = {}
	for x in a:
		if x in vals:
			vals[x] += 1
		else:
			vals[x] = 1
	tot = sum(a)
	lessValues = 0
	for i in range(n):
		if i not in vals:
			mini = n - lessValues
			maxi = n * n - tot + (n - lessValues)
		else:
			mini = n - vals[i] - lessValues
			worktot = tot - i * vals[i]
			maxi = n * n - worktot - vals[i] * n + (n - lessValues - vals[i])
			lessValues += vals[i]
		print(str(mini) + ' ' + str(maxi))


def update(D, l, r, x):
	D[l] += x
	D[r + 1] -= x
t = int(input())
for tt in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	a1 = [0] * (n + 1)
	a2 = [0] * (n + 1)
	for r in range(n):
		if a[r] >= 1 and a[r] < n:
			update(a1, a[r] + 1, n - 1, n - a[r])
			update(a1, 0, a[r] - 1, n - a[r] + 1)
			update(a2, 0, a[r] - 1, 1)
		elif a[r] == n:
			update(a2, 0, a[r] - 1, 1)
			update(a1, 0, n - 1, 1)
		else:
			update(a1, a[r] + 1, n - 1, n - a[r])
	for i in range(1, n):
		a1[i] += a1[i - 1]
		a2[i] += a2[i - 1]
	for j in range(n):
		print(a2[j], a1[j])


from collections import defaultdict
import bisect
for _ in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	d = defaultdict(int)
	ans = []
	l.sort()
	for i in l:
		d[i] += 1
	count = 0
	for i in range(n):
		count += n - l[i]
	for i in range(n):
		w = n - bisect.bisect(l, i)
		x = w
		y = count - (n - i) * d[i] + w
		ans.append([x, y])
	for i in ans:
		print(*i)


import sys
import math

def printt(ans):
	for i in range(0, len(ans)):
		print(ans[i][0], ans[i][1])
t = int(input())
while t > 0:
	t = t - 1
	n = int(input())
	arr = list(map(int, input().split()))
	minn = n
	res = [0] * (minn + 5)
	w = 0
	vec = []
	ans = []
	k_v = [0] * (minn + 5)
	for i in range(0, minn):
		temp = arr[i]
		b = minn - temp
		if res[temp] == None:
			res[temp] = 1
			vec.append(res[temp])
		else:
			res[temp] = res[temp] + 1
			if len(vec) != 0:
				vec.pop(0)
		if k_v[temp] == None:
			k_v[temp] = b
			vec.append(res[temp])
		else:
			k_v[temp] = k_v[temp] + b
		w = w + b
	fin = res
	for i in range(minn, -1, -1):
		c = fin[i + 1]
		if c:
			fin[i] = fin[i] + c
		else:
			vec.append(1)
	for i in range(0, minn):
		c = fin[i + 1]
		y = w - k_v[i] + c
		x = c
		q = []
		vec.append(c)
		q.append(x)
		q.append(y)
		ans.append(q)
	printt(ans)


for _ in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split()))
	res = 0
	(arr1, arr2) = ([0] * (n + 9), [0] * (n + 9))
	for i in range(n):
		temp = n - arr[i]
		arr1[arr[i]] += 1
		arr2[arr[i]] += temp
		res += temp
	arr3 = arr1.copy()
	for i in range(n, -1, -1):
		arr3[i] += arr3[i + 1]
	for i in range(0, n):
		ans1 = res - arr2[i] + arr3[i + 1]
		ans = arr3[i + 1]
		print(ans, ans1)
	count = 0
	for i in range(n):
		count += 1
	for i in range(n):
		count -= 1


from math import inf
from collections import *
import math, os, sys, heapq, bisect, random, threading
from functools import lru_cache
from itertools import *

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

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

def inpu():
	return int(inp())

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

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

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

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

def fsep():
	return map(float, inp().split())
(M, M1) = (1000000007, 998244353)

def main():
	how_much_noob_I_am = 1
	how_much_noob_I_am = inpu()
	for _ in range(how_much_noob_I_am):
		n = inpu()
		arr = lis()
		p = sorted(arr)
		ans = []
		blankp = []
		for i in p:
			blankp.append(n - i)
		blank = list(accumulate(blankp))
		blankp.reverse()
		blank2 = list(accumulate(blankp))
		blank2.insert(0, 0)
		blank.insert(0, 0)
		for i in range(n):
			ind = bisect.bisect(p, i)
			min1 = n - ind
			ind2 = bisect.bisect_left(p, i)
			max1 = blank2[min1] + min1 + blank[ind2]
			ans.append([min1, max1])
		for i in ans:
			print(*i)
main()


for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	a.sort()
	sumVal = sum(a)
	j = 0
	for i in range(n):
		while j < n and a[j] < i:
			j += 1
		k = j
		if j < n and i == a[j]:
			while k < n and a[k] == i:
				k += 1
			k -= 1
		if j < n and i == a[j]:
			print(n - k - 1, n * (n - (k - j + 1)) - (sumVal - i * (k - j + 1)) + n - k - 1)
		else:
			print(n - j, n * n - sumVal + n - j)


for h in range(int(input())):
	n = int(input())
	x = list(map(int, input().split()))
	sure = [0] * n
	r = [0] * n
	l = [0] * n
	for i in x:
		if i + 1 < n:
			r[i + 1] += n - i
		if i - 1 >= 0:
			l[i - 1] += n - i
		if i - 1 >= 0:
			sure[i - 1] += 1
	for i in range(len(sure) - 2, -1, -1):
		sure[i] += sure[i + 1]
		l[i] += l[i + 1]
	for i in range(1, len(r)):
		r[i] += r[i - 1]
	for i in range(n):
		print(sure[i], sure[i] + r[i] + l[i], end=' ')
		print('')


T = int(input())
for tr in range(T):
	N = int(input())
	A = list(map(int, input().split(' ')))
	BCount = [0] * (N + 1)
	Bmin = [-1] * N
	Bmax = [-1] * N
	for i in range(N):
		BCount[A[i]] += 1
	Nmin = N
	Nmax = 0
	for i in range(N):
		Nmin -= BCount[i]
		Nmax += BCount[i] * (N - i)
		Bmin[i] = Nmin
	for i in range(N):
		Bmax[i] = Nmax - BCount[i] * (N - i) + Bmin[i]
	for i in range(N):
		print(Bmin[i], Bmax[i])


from bisect import bisect_left, bisect_right
for _ in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split()))
	arr.sort()
	pre = [0]
	curr = 0
	for i in range(n):
		curr += arr[i]
		pre.append(curr)
	for i in range(n):
		l = bisect_left(arr, i)
		r = bisect_right(arr, i)
		a = n - r
		b = l * n - pre[l] + (n - r) * (n + 1) - (pre[n] - pre[r])
		print(a, b)


from sys import stdin, stdout
input = stdin.readline
import bisect
t = int(input())
for _ in range(t):
	n = int(input())
	a = [int(x) for x in input().split()]
	a = sorted(a)
	pre = [a[0] for i in range(n)]
	for i in range(1, n):
		pre[i] = pre[i - 1] + a[i]
	ans1 = [0 for i in range(n)]
	ans2 = [0 for i in range(n)]
	for i in range(n):
		ind = bisect.bisect_left(a, i)
		ind -= 1
		if ind >= 0:
			ans2[i] = (ind + 1) * n - pre[ind]
		ind = bisect.bisect_right(a, i)
		ans2[i] += (n - ind) * n - (pre[-1] - (pre[ind - 1] if ind else 0)) + (n - ind)
		ans1[i] = n - ind
	for i in range(n):
		print(ans1[i], ans2[i])


import sys
input = sys.stdin.readline
for _ in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split()))
	least = (n + 1) * [0]
	most = (n + 69) * [0]
	for x in arr:
		least[0] += 1
		most[0] += n - x + 1
		least[x] -= 1
		most[x] -= n - x + 1
		most[x + 1] += n - x
	for i in range(n):
		if i:
			least[i] += least[i - 1]
			most[i] += most[i - 1]
		print(least[i], most[i])


from bisect import bisect_right
from collections import defaultdict
for _ in range(int(input())):
	n = int(input())
	p = 0
	arr = list(map(int, input().split()))
	d = defaultdict(int)
	for el in arr:
		d[el] += n - el
		p += n - el
	arr.sort()
	for i in range(0, n):
		ind = bisect_right(arr, i)
		le = n - ind
		me = le + p - d[i]
		print(le, me)


for _ in range(int(input())):
	n = int(input())
	a = [*map(int, input().split())]
	q = [0] * (n + 1)
	r = 0
	w = [0] * (n + 1)
	for i in range(n):
		q[a[i]] += 1
		w[a[i]] += n - a[i]
	r = sum(w)
	for i in range(n):
		q[n - 1 - i] += q[n - i]
	for i in range(n):
		print(q[i + 1], q[i + 1] + r - w[i])


from collections import defaultdict
from bisect import bisect_right
for _ in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	l.sort()
	d = defaultdict(lambda : 0)
	d1 = defaultdict(lambda : 0)
	for i in range(n):
		d1[i] = n - bisect_right(l, i)
	s = 0
	for i in l:
		d[i] += 1
		s += max(0, n - i)
	for i in range(n):
		print(d1[i], d1[i] + s - d[i] * max(0, n - i))


import bisect
t = int(input())
for _ in range(t):
	n = int(input())
	arr = list(map(int, input().strip().split()))
	arr.sort()
	freq = [0 for _ in range(n + 1)]
	extras = 0
	for i in range(n):
		freq[arr[i]] += 1
		extras += n - arr[i]
	for i in range(n):
		ans = [0, 0]
		index = bisect.bisect_right(arr, i)
		ans[0] = n - index
		ans[1] = ans[0] + extras - freq[i] * (n - i)
		print(*ans)


t = int(input())
for k in range(t):
	n = int(input())
	mex = input().split(' ')
	for i in range(n):
		mex[i] = int(mex[i])
	mex.sort()
	pref_l = [mex[0]]
	cur_l = mex[0]
	pref_r = [mex[len(mex) - 1]] * n
	cur_r = mex[len(mex) - 1]
	for i in range(1, len(mex)):
		cur_l += mex[i]
		pref_l.append(cur_l)
	for i in range(len(mex) - 2, -1, -1):
		cur_r += mex[i]
		pref_r[i] = cur_r
	for i in range(n):
		t = i
		l = 0
		r = len(mex) - 1
		ind = -1
		while l <= r:
			mid = l + (r - l) // 2
			if mex[mid] <= t:
				l = mid + 1
			else:
				ind = mid
				r = mid - 1
		l = 0
		r = len(mex) - 1
		ind1 = -1
		while l <= r:
			mid = l + (r - l) // 2
			if mex[mid] >= t:
				r = mid - 1
			else:
				ind1 = mid
				l = mid + 1
		least = 0
		most = 0
		if ind == -1:
			least = 0
		else:
			least += len(mex) - 1 - ind + 1
		if ind == -1 and ind1 == -1:
			most = 0
		elif ind != -1 and ind1 == -1:
			most += n * (len(mex) - 1 - ind + 1) - pref_r[ind] + (len(mex) - 1 - ind + 1)
		elif ind == -1 and ind1 != -1:
			most += n * (ind1 + 1) - pref_l[ind1]
		else:
			most += n * (len(mex) - 1 - ind + 1) - pref_r[ind] + (len(mex) - 1 - ind + 1) + (n * (ind1 + 1) - pref_l[ind1])
		print(str(least) + ' ' + str(most))


for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	reqd = [0] * (n + 1)
	bad = [0] * (n + 1)
	extra = 0
	for x in a:
		if x > 0:
			reqd[x - 1] += 1
		bad[x] += n - x
		extra += n - x
	for i in range(n):
		reqd[n - i - 1] += reqd[n - i]
	for i in range(n):
		print(reqd[i], reqd[i] + extra - bad[i])


import sys
from os import path
from math import gcd
from bisect import bisect_left, bisect_right
if path.exists('input.txt'):
	sys.stdin = open('input.txt', 'r')
	sys.stdout = open('output.txt', 'w')

def countGreater(arr, k):
	n = len(arr)
	l = 0
	r = n - 1
	ind = 0
	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

def countLesser(arr, k):
	n = len(arr)
	l = 0
	r = n - 1
	ans = -1
	while l <= r:
		mid = int(l + (r - l) / 2)
		if arr[mid] >= k:
			r = mid - 1
		else:
			ans = mid
			l = mid + 1
	return ans + 1

def pos(arr, k):
	a = bisect_right(arr, k)
	if a == len(arr):
		if arr[a - 1] == k:
			return a - 1
		return -1
	if arr[a] > k:
		a -= 1
	return a
for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	sorteda = sorted(a)
	greater = {}
	for i in range(n):
		greater[i] = countGreater(sorteda, i)
	ans = {}
	prefix = [0] * n
	prefix[0] = sorteda[0]
	for i in range(1, n):
		prefix[i] += sorteda[i] + prefix[i - 1]
	for i in range(n):
		if i == 99:
			ksdj = 0
		p = pos(sorteda, i)
		s = prefix[-1]
		if p != -1:
			s -= prefix[p]
		ans[i] = (0, 0)
		less = countLesser(sorteda, i)
		ans[i] = (greater[i], less * n - prefix[less - 1])
		if ans[i][1] < 0:
			ans[i] = (0, 0)
		if greater[i] > 0:
			ans[i] = (greater[i], ans[i][1] + greater[i] * n - s + greater[i])
	for i in ans:
		print(ans[i][0], ans[i][1])


for _ in range(int(input())):
	n = int(input())
	arr = sorted(list(map(int, input().split())))
	freq = [0 for i in range(n + 1)]
	atleast = [0 for i in range(n)]
	extra = sum([n - e for e in arr])
	for e in arr:
		freq[e] += 1
	tmp = 0
	for i in range(n, 0, -1):
		tmp += freq[i]
		atleast[i - 1] = tmp
	for i in range(n):
		print(atleast[i], atleast[i] + extra - freq[i] * (n - i))


for _ in range(int(input())):
	n = int(input())
	arr = sorted(list(map(int, input().split())))
	countI = [0 for i in range(n + 1)]
	minX = [0 for i in range(n)]
	maxX = sum([n - e for e in arr])
	for e in arr:
		countI[e] += 1
	tmp = 0
	for i in range(n, 0, -1):
		tmp += countI[i]
		minX[i - 1] = tmp
	for i in range(n):
		print(minX[i], '', minX[i] + maxX - (n - i) * countI[i])


t = int(input())
for _ in range(t):
	n = int(input())
	arr = list(map(int, input().split()))
	atleast = [0 for i in range(n)]
	atmost = [0 for i in range(n)]
	d = {}
	for ele in arr:
		d[ele] = d.get(ele, 0) + 1
	atleast[0] = n - d.get(0, 0)
	for i in range(1, n):
		atleast[i] = atleast[i - 1] - d.get(i, 0)
		atleast[i] = max(0, atleast[i])
	tm = n * n - sum(arr)
	for i in range(n):
		atmost[i] = tm + atleast[i] - d.get(i, 0) * (n - i)
	for i in range(n):
		(a, b) = (atleast[i], atmost[i])
		print(a, b)


import bisect
test = int(input())
while test:
	n = int(input())
	frequency = dict()
	a = [int(x) for x in input().split()]
	extra = 0
	for i in a:
		extra += n - i
		if i in frequency:
			frequency[i] += 1
		else:
			frequency[i] = 1
	a.sort()
	for i in range(n):
		k = bisect.bisect_right(a, i)
		try:
			print(n - k, n - k + extra - frequency[i] * (n - i))
		except KeyError:
			print(n - k, n - k + extra)
	test -= 1


import bisect
test = int(input())
while test:
	n = int(input())
	frequency = [0] * (n + 1)
	extra = 0
	a = [int(x) for x in input().split()]
	for i in a:
		extra += n - i
		frequency[i] += 1
	a.sort()
	for i in range(n):
		k = bisect.bisect_right(a, i)
		print(n - k, n - k + extra - frequency[i] * (n - i))
	test -= 1


t = int(input())
while t > 0:
	n = int(input())
	a = [int(x) for x in input().split()]
	blanks = sum([n - i for i in a])
	countI = [0 for i in range(n + 1)]
	minR = [0 for i in range(n)]
	for i in range(n):
		countI[a[i]] += 1
	r = 0
	for i in range(n, 0, -1):
		r += countI[i]
		minR[i - 1] = r
	for i in range(n):
		print(minR[i], ' ', minR[i] + blanks - countI[i] * (n - i))
	t -= 1


for t in range(int(input())):
	n = int(input())
	mex = list(map(int, input().strip().split()))
	mex.sort()
	freq = [0 for i in range(n + 1)]
	atl = []
	atm = []
	extra = 0
	for m in mex:
		freq[m] += 1
		extra += n - m
	j = 0
	for i in range(n):
		j += freq[i]
		atl.append(n - j)
		atm.append(extra + atl[i] - freq[i] * (n - i))
	print('\n'.join(map(lambda x, y: f'{x} {y}', atl, atm)))


import sys
import os
import math
import collections
T = int(input())
for _ in range(T):
	N = int(input())
	A = list(map(int, input().split()))
	(B, C) = ([0] * (N + 1), [0] * (N + 1))
	for i in range(N):
		if A[i] != 0:
			B[A[i] - 1] += 1
	for i in range(N - 1, -1, -1):
		B[i] = B[i] + B[i + 1]
	ans = 0
	for i in range(N):
		ans += N - A[i]
		C[A[i]] += N - A[i]
	for i in range(N):
		print(B[i], ans - C[i] + B[i])


for _ in range(int(input())):
	n = int(input())
	min1 = [0] * (n + 1)
	max1 = [0] * (n + 1)
	l = list(map(int, input().split()))
	for i in l:
		if i > 0:
			min1[i - 1] += 1
		if i != 0:
			max1[0] += n - i + 1
			max1[i] -= n - i + 1
			if i < n:
				max1[i + 1] += n - i
		else:
			max1[1] += n - i
	for i in range(n - 1, -1, -1):
		min1[i] += min1[i + 1]
	for i in range(1, n):
		max1[i] += max1[i - 1]
	for i in range(n):
		print(min1[i], max1[i])


from math import *
import sys

def input():
	return sys.stdin.readline().replace('\n', '').strip()
sys.setrecursionlimit(10 ** 9)
for _ in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	l1 = [0 for i in range(n + 1)]
	l2 = [0 for i in range(n + 1)]
	_sum = 0
	for i in range(n):
		l1[l[i]] += 1
		_sum += l[i]
	left_out = n * n - _sum
	for i in range(n - 1, -1, -1):
		l2[i] += l2[i + 1] + l1[i + 1]
	l3 = [0 for i in range(n + 1)]
	for i in range(n + 1):
		l3[i] = l2[i] + left_out - l1[i] * (n - i)
	for i in range(n):
		print(l2[i], l3[i])


t = int(input())
for i in range(t):
	N = int(input())
	k1 = list(map(int, input().split()))
	LPB = [0] * (N + 5)
	UPB = [0] * (N + 5)
	value = 0
	for i in range(N):
		b = N - k1[i]
		LPB[k1[i]] += 1
		UPB[k1[i]] += b
		value += b
	short = LPB
	for i in range(N, -1, -1):
		short[i] += short[i + 1]
	for i in range(N):
		y = value - UPB[i] + short[i + 1]
		x = short[i + 1]
		print(x, y)


import math
from bisect import bisect, bisect_left, bisect_right
import heapq
from math import gcd, floor, sqrt, log
from collections import defaultdict as ddc
from collections import Counter

def intin():
	return int(input())

def mapin():
	return map(int, input().split())

def strin():
	return input().split()
INF = 10 ** 20
mod = 1000000007

def LIS(arr, n):
	dp = [10 ** 9] * (n + 1)
	for ele in arr:
		dp[bisect_left(dp, ele)] = ele
	return bisect_left(dp, 10 ** 9)

def exponentiation(bas, exp, mod=1000000007):
	t = 1
	while exp > 0:
		if exp % 2 != 0:
			t = t * bas % mod
		bas = bas * bas % mod
		exp //= 2
	return t % mod

def MOD(p, q=1, mod=1000000007):
	expo = 0
	expo = mod - 2
	while expo:
		if expo & 1:
			p = p * q % mod
		q = q * q % mod
		expo >>= 1
	return p
yes = 'YES'
no = 'NO'
even = 'EVEN'
odd = 'ODD'

def process(arr, n):
	C = Counter(arr)
	A = len(arr)
	MIN = [0] * n
	for i in range(n):
		A -= C[i]
		MIN[i] = A
	MAX = [0] * n
	available = 0
	this = 0
	for ele in arr:
		if ele == 0:
			this += n
		else:
			available += n - (ele - 1)
	MAX[0] = available
	for i in range(1, n):
		temp = (n - i) * C[i]
		available = available - (n - i + 1) * C[i]
		available += this
		MAX[i] = available
		this = temp
	for i in range(n):
		print(MIN[i], MAX[i])

def main():
	for _ in range(int(input())):
		n = intin()
		arr = list(mapin())
		process(arr, n)
main()


t = int(input())
for _ in range(t):
	n = int(input())
	arr = list(map(int, input().split()))
	minn = [0] * (n + 1)
	maxl = [0] * (n + 1)
	maxr = [0] * (n + 1)
	for each in arr:
		minn[0] += 1
		minn[each] -= 1
		maxl[0] += n - each + 1
		maxl[each] -= n - each + 1
		maxr[n - 1] += n - each
		maxr[each] -= n - each
	for i in range(1, n + 1):
		minn[i] += minn[i - 1]
		maxl[i] += maxl[i - 1]
	for i in range(n - 1, -1, -1):
		maxr[i] += maxr[i + 1]
	for i in range(n):
		print(minn[i], maxl[i] + maxr[i])


t = int(input())
for ti in range(t):
	n = int(input())
	mex = list(map(int, input().split()))
	mexcount = [0] * (n + 1)
	for m in mex:
		mexcount[m] = mexcount[m] + 1
	mexsum = [0] * (n + 1)
	mexcountsum = [0] * (n + 1)
	mexsum[0] = 0
	mexcountsum[0] = mexcount[0]
	for i in range(1, n + 1):
		mexsum[i] = mexsum[i - 1] + mexcount[i] * i
		mexcountsum[i] = mexcountsum[i - 1] + mexcount[i]
	for i in range(n):
		min_ = mexcountsum[n] - mexcountsum[i]
		max_ = (1 + n) * min_ - mexsum[n] + mexsum[i]
		if i != 0:
			max_ = max_ + n * mexcountsum[i - 1] - mexsum[i - 1]
		print(min_, max_)


from operator import itemgetter
from sys import maxsize, stdin
from collections import Counter, defaultdict
from math import log
import ctypes
import itertools
t = int(stdin.readline().strip())
while t > 0:
	n = int(stdin.readline().strip())
	arr = list(map(int, stdin.readline().strip().split(' ')))
	temp1 = [0] * (n + 1)
	temp2 = [0] * (n + 1)
	temp3 = [0] * (n + 1)
	temp1[:] = itertools.repeat(0, len(temp1))
	temp2[:] = itertools.repeat(0, len(temp2))
	temp3[:] = itertools.repeat(0, len(temp3))
	for i in range(n):
		temp1[0] += 1
		temp1[arr[i]] -= 1
		temp2[0] += n - arr[i] + 1
		temp2[arr[i]] -= n - arr[i] + 1
		temp3[n - 1] += n - arr[i]
		temp3[arr[i]] -= n - arr[i]
	for i in range(1, n + 1):
		temp1[i] += temp1[i - 1]
		temp2[i] += temp2[i - 1]
	for i in range(n - 2, -1, -1):
		temp3[i] += temp3[i + 1]
	for i in range(n):
		print(temp1[i], temp2[i] + temp3[i])
	t -= 1


case = int(input())
for i in range(case):
	n = 0
	x = 0
	n = int(input())
	lst = list(map(int, input().split(' ')))
	lst8 = [0] * (n + 1)
	lst4 = [0] * (n + 1)
	arr = [0] * (n + 1)
	for i in range(n):
		x = lst[i]
		lst8[0] += 1
		lst8[x] -= 1
		lst4[0] += n - x + 1
		lst4[x] -= n - x + 1
		arr[n - 1] += n - x
		arr[x] -= n - x
	for i in range(1, n + 1):
		lst8[i] += lst8[i - 1]
		lst4[i] += lst4[i - 1]
	for i in range(n - 1, -1, -1):
		arr[i] += arr[i + 1]
	for i in range(n):
		x = lst4[i] + arr[i]
		print(lst8[i], end=' ')
		print(x)


import sys
import math
from itertools import *
from queue import LifoQueue
from bisect import bisect
from collections import deque, Counter, defaultdict
mod = 10 ** 9 + 7

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

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

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

def rls():
	return list(map(str, input().split()))

def rm():
	return map(int, input().split())

def isPowerOfTwo(x):
	return x and (not x & x - 1)

def freq(a):
	return Counter(a)

def lcm(x, y):
	return x * y // gcd(x, y)

def d2b(n):
	s = bin(n).replace('0b', '')
	return (34 - len(s)) * '0' + s

def BS(a, x):
	i = bisect.bisect_left(a, x)
	if i != len(a) and a[i] == x:
		return i
	else:
		return -1

def gcd(x, y):
	while y:
		(x, y) = (y, x % y)
	return x
for _ in range(ri()):
	n = ri()
	a = rl()
	l = [0] * (n + 1)
	for i in a:
		l[i] += 1
	min_l = l.copy()
	for i in range(n - 1, -1, -1):
		min_l[i] += min_l[i + 1]
	max1 = l.copy()
	max1[-1] = max1[-1]
	for i in range(n - 1, -1, -1):
		max1[i] = l[i] * (n - i + 1) + max1[i + 1]
	max2 = l.copy()
	max2[0] = max2[0] * n
	for i in range(1, n + 1):
		max2[i] = l[i] * (n - i) + max2[i - 1]
	print(min_l[1], max1[1])
	for i in range(2, n + 1):
		print(min_l[i], max1[i] + max2[i - 2])


case = int(input())
for i in range(case):
	n = 0
	x = 0
	n = int(input())
	lst = list(map(int, input().split(' ')))
	minn = [0] * (n + 1)
	maxxl = [0] * (n + 1)
	maxxr = [0] * (n + 1)
	for i in range(n):
		x = lst[i]
		minn[0] += 1
		minn[x] -= 1
		maxxl[0] += n - x + 1
		maxxl[x] -= n - x + 1
		maxxr[n - 1] += n - x
		maxxr[x] -= n - x
	for i in range(1, n + 1):
		minn[i] += minn[i - 1]
		maxxl[i] += maxxl[i - 1]
	for i in range(n - 1, -1, -1):
		maxxr[i] += maxxr[i + 1]
	for i in range(n):
		x = maxxl[i] + maxxr[i]
		print(minn[i], end=' ')
		print(x)


for _ in range(int(input())):
	N = int(input())
	mex = list(map(int, input().split()))
	lower_bound = [0] * (N + 5)
	upper_bound = [0] * (N + 5)
	value = 0
	for i in range(N):
		b = N - mex[i]
		lower_bound[mex[i]] += 1
		upper_bound[mex[i]] += b
		value += b
	short = lower_bound
	for i in range(N, -1, -1):
		short[i] += short[i + 1]
	for i in range(N):
		y = value - upper_bound[i] + short[i + 1]
		x = short[i + 1]
		print(x, y)


for _ in range(int(input())):
	n = int(input())
	li = list(map(int, input().split()))
	presum = [0] * n
	maxl = [0] * n
	maxr = [0] * n
	for i in range(n):
		maxl[0] += n - li[i] + 1
		maxr[-1] += n - li[i]
		if li[i] < n:
			presum[li[i]] -= 1
			maxl[li[i]] -= n - li[i] + 1
			maxr[li[i]] -= n - li[i]
	presum[0] += n
	for i in range(1, n):
		presum[i] += presum[i - 1]
		maxl[i] += maxl[i - 1]
	for i in range(n - 2, -1, -1):
		maxr[i] += maxr[i + 1]
	for i in range(n):
		x = maxl[i] + maxr[i]
		print(presum[i], x)


def main():
	n = int(input())
	arr = list(map(int, input().split()))
	mn = [0] * (n + 1)
	mx = [0] * (n + 1)
	mxr = [0] * (n + 1)
	for i in range(n):
		a = arr[i]
		mn[0] += 1
		mn[a] -= 1
		mx[0] += n - a + 1
		mx[a] -= n - a + 1
		mxr[n - 1] += n - a
		mxr[a] -= n - a
	for i in range(1, n + 1):
		mn[i] += mn[i - 1]
		mx[i] += mx[i - 1]
	i = n - 1
	while i >= 0:
		mxr[i] += mxr[i + 1]
		i -= 1
	for i in range(n):
		print(mn[i], mx[i] + mxr[i])
	return
for _ in range(int(input())):
	main()


t = int(input())
for _ in range(t):
	n = int(input())
	arr = list(map(int, input().split()))
	a = [0] * (n + 1)
	b = [0] * (n + 1)
	c = [0] * (n + 1)
	for i in arr:
		a[0] += 1
		a[i] -= 1
		b[0] += n - i + 1
		b[i] -= n - i + 1
		c[n - 1] += n - i
		c[i] -= n - i
	for i in range(1, n + 1, 1):
		a[i] += a[i - 1]
		b[i] += b[i - 1]
	for i in range(n - 1, -1, -1):
		c[i] += c[i + 1]
	for i in range(n):
		print(a[i], b[i] + c[i], sep=' ', end='\n')


def func():
	inp1 = int(input())
	let_dp = [0] * (inp1 + 5)
	let_dp1 = [0] * (inp1 + 5)
	count = 0
	list_ = list(map(int, input().split()))
	for i in list_:
		var_b = inp1 - i
		let_dp[i] += 1
		let_dp1[i] += var_b
		count += var_b
	var_c = let_dp
	for i in reversed(range(inp1)):
		var_c[i] += var_c[i + 1]
	for i in range(inp1):
		var_y = count - let_dp1[i] + var_c[i + 1]
		var_x = var_c[i + 1]
		print(var_x, var_y)
for i in range(int(input())):
	func()


t = int(input())
for i in range(0, t):
	n = int(input())
	a = list(map(int, input().split()))
	d = dict()
	maxans1 = [0] * (n + 1)
	maxans2 = [0] * (n + 1)
	minans = [0] * (n + 1)
	for j in range(0, len(a)):
		if a[j] not in d.keys():
			d[a[j]] = 1
		else:
			d[a[j]] = d[a[j]] + 1
		if a[j] != 0:
			maxans1[0] = maxans1[0] + (n - (a[j] - 1))
			minans[0] = minans[0] + 1
		maxans2[n] = maxans2[n] + (n - a[j])
	for j in range(1, n):
		if j in d.keys():
			maxans1[j] = maxans1[j - 1] - d[j] * (n - (j - 1))
			minans[j] = minans[j - 1] - d[j]
		else:
			maxans1[j] = maxans1[j - 1]
			minans[j] = minans[j - 1]
	for j in range(n - 1, -1, -1):
		if j in d.keys():
			maxans2[j] = maxans2[j + 1] - d[j] * (n - j)
		else:
			maxans2[j] = maxans2[j + 1]
	for j in range(0, n):
		print(minans[j], end=' ')
		print(maxans1[j] + maxans2[j])


t = int(input())
while t > 0:
	t -= 1
	n = int(input())
	a = [int(x) for x in input().split()]
	h = [0 for x in range(n + 1)]
	d = [0 for x in range(n + 1)]
	post = [0 for x in range(n + 1)]
	h[0] = n
	for i in range(n):
		x = a[i]
		h[x] -= 1
		d[x] = d[x] - n + x - 1
		post[x] = post[x] - n + x
		d[0] += n - x + 1
		post[n - 1] += n - x
	for i in range(1, n + 1):
		d[i] += d[i - 1]
	for i in range(1, 1 + n):
		h[i] += h[i - 1]
	for i in range(n - 1, -1, -1):
		post[i] += post[i + 1]
	for i in range(n):
		x = h[i]
		(m1, m2) = (0, 0)
		print(h[i], d[i] + post[i])


for _ in range(int(input())):
	n = int(input())
	temp1 = [0] * (n + 5)
	temp2 = [0] * (n + 5)
	l = list(map(int, input().split()))
	for i in range(n):
		temp1[l[i]] += 1
		temp2[l[i]] += n - l[i]
	for i in range(n, -1, -1):
		temp1[i] += temp1[i + 1]
	ans = n * n - sum(l)
	for i in range(n):
		print(temp1[i + 1], ans + temp1[i + 1] - temp2[i])


import sys
input = lambda : sys.stdin.readline()
T = int(input())
for _ in range(T):
	n = int(input().strip())
	a = list(map(int, input().strip().split()))
	a.sort()
	a2 = []
	dic = {}
	for i in a:
		if i not in dic.keys():
			dic[i] = 1
			if a2 != n:
				a2.append(i)
		else:
			dic[i] += 1
	L = [n for i in range(n)]
	j = 0
	if a[j] == 0:
		L[0] -= dic[0]
		j += 1
	for i in range(1, n):
		if j == len(a2):
			L[i] = L[i - 1]
			continue
		if i != a2[j]:
			L[i] = L[i - 1]
		else:
			L[i] = L[i - 1] - dic[a2[j]]
			j += 1
	y = n * n - sum(a)
	M = [y for i in range(n)]
	for i in range(n):
		if a[i] != n:
			M[a[i]] -= n - a[i]
	for i in range(n):
		x = L[i]
		y = M[i] + x
		print(x, y)


t = int(input())
for k in range(t):
	n = int(input())
	l = list(map(int, input().split()))
	minn = [0] * (n + 1)
	maxxl = [0] * (n + 1)
	maxxr = [0] * (n + 1)
	for i in range(n):
		x = l[i]
		minn[0] += 1
		minn[x] -= 1
		maxxl[0] += n - x + 1
		maxxl[x] -= n - x + 1
		maxxr[n - 1] += n - x
		maxxr[x] -= n - x
	for i in range(1, n + 1):
		minn[i] += minn[i - 1]
		maxxl[i] += maxxl[i - 1]
	for i in range(n - 1, -1, -1):
		maxxr[i] += maxxr[i + 1]
	for i in range(0, n):
		xx = maxxl[i] + maxxr[i]
		print(str(minn[i]) + ' ' + str(xx))