# MAKEPERM - Editorial

Author: raysh07
Tester: airths
Editorialist: iceknight1093

TBD

None

# PROBLEM:

You’re given an array A of length N.
Does there exist another array B of length N such that the array C which has C_i = A_i +B_i is a permutation?

# EXPLANATION:

The array B essentially allows us to increase each element of A as much as we like, since it contains non-negative integers.

The final array, after all increases have been done, should contain one occurrence each of 1, 2, 3, \ldots, N.
So,

• Some element of A should be increased to reach 1.
This is only possible if the chosen A_i is itself initially \leq 1.
In particular, the smallest element of A should be \leq 1.
• Some element of A (other than the one chosen above) should be increased to reach 2.
Again, this means A should contain an element that’s \leq 2 other than the one that’s chosen to be 1.
Notice that this means that the second-smallest element of A should be \leq 2.
• Some element of A should be increased to 3 - so the third-smallest element of A should be \leq 3.
\vdots
• More generally, for any k, the k-th smallest element of A should be \leq k.

So, the condition we’re looking for is, quite simply, that for every k from 1 to N, the k-th smallest element of A shouldn’t exceed k.

This condition is easy to check: sort A and then check whether A_i \leq i for every i.
The constraints are small enough that a quadratic implementation that repeatedly extracts and deletes the minimum element is also fast enough to get AC.

# TIME COMPLEXITY:

\mathcal{O}(N)\sim \mathcal{O}(N^2) per testcase.

# CODE:

Editorialist's code (Python)
for _ in range(int(input())):
n = int(input())
a = list(map(int, input().split()))
ans = 'Yes'
for i in range(1, n+1):
mn = min(a)
if mn > i: ans = 'No'
a.remove(mn)
print(ans)