[Solution] Atleast and Atmost CodeChef Solution

[Solution] Atleast and Atmost CodeChef Solution

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

Ashish likes lower bounds and Kryptonix likes upper bounds. So, for each 0≤i≤N−1$0\le i\le N-1$, find:

• The least possible number of occurrences of i$i$ across all the arrays
• The most possible number of occurrences of i$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.

Solution Click Below:-  CLICK HERE

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]$[0,2,4,1,1,5]$ is 3$3$, and the mex of [3,8,101,99,100]$[3,8,101,99,100]$ is 0$0$.

Input Format

• The first line of input contains a single integer T$T$ — the number of test cases. Then the test cases follow.
• The first line of each test case contains an integer N$N$ — the size of the array.
• The second line of each test case contains N$N$ space-separated integers A1,A2,…,AN$A_1,A_2,\dots ,A_N$, denoting

Biryani classes CodeChef Solution

Atleast and Atmost CodeChef Solution

The Attack of Knight CodeChef Solution

Air Hockey CodeChef Solution 

Jogging CodeChef Solution

Triple Xor CodeChef Solution

Dense Bracket Sequence CodeChef Solution

Alternating Strings CodeChef Solution

•  the mexes of the N$N$ arrays.

Output Format

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

Constraints

• 1≤T≤104$1\le T\le {10}^4$
• 1≤N≤3⋅105$1\le N\le 3\cdot {10}^5$
• 0≤Ai≤N$0\le A_i\le N$
• The sum of N$N$ over all test cases does not exceed 3⋅