# PROBLEM LINK:

Practice

Contest: Division 1

Contest: Division 2

Contest: Division 3

Contest: Division 4

* Author:* raysh07

*airths*

**Tester:***iceknight1093*

**Editorialist:**# DIFFICULTY:

TBD

# PREREQUISITES:

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