## GUPTA MECHANICAL

IN THIS WEBSITE I CAN TELL ALL ABOUT TECH. TIPS AND TRICKS APP REVIEWS AND UNBOXINGS ALSO TECH. NEWS .............

## [Solution] Atleast and Atmost CodeChef Solution

There are $N$ hidden integer arrays of length $N$ length 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\le i\le 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 $\left[0,2,4,1,1,5\right]$ is $3$, and the mex of $\left[3,8,101,99,100\right]$ 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\le T\le {10}^{4}$
• $1\le N\le 3\cdot {10}^{5}$
• $0\le {A}_{i}\le N$
• The sum of $N$ over all test cases does not exceed