### PROBLEM LINK:

**Author and Editorialist:** Lalit Kundu

**Tester:** Kamil Debowski

### DIFFICULTY:

simple

### PREREQUISITES:

logic, basic programming, sorting

### PROBLEM:

You are given a list of integers A_1, A_2, ..., A_N. You have to rearrange them to get B_1, B_2, ..., B_N. Also, the conditions that |B_i - B_{i + 1}| \le 1 should be satisfied \forall i < N.

You have to output if it’s possible to do so.

### QUICK EXPLANATION:

======================

If in sorted array A, any two adjacent elements differ by more than 1, answer is `NO`

, otherwise `YES`

.

### EXPLANATION:

================

**Claim** : If in sorted array A, any two adjacent elements differ by more than 1, answer is `NO`

, otherwise `YES`

.

**Proof**: Let’s assume there are two elements l and r in array A, where r - l > 1 and no other element lies between l and r. We have to show that there doesn’t exist a permutation of A where adjacent elements don’t differ by more than 1, no matter what the other elements of array A are.

We assume there exists such a permutation. Then, there are two cases:

- l occurs before r in this permutation. Since each adjacent element differs by atmost 1, we can observe that we have to go from element l to r and in each step we can either remain at same value or increase by one or decrease by one, with the condition that new value should be present in array A. The only way to reach r is through r-1(since l occurs before r in array), which can’t be achieved since there is no such value in the array A.
- r occurs before l in this permutation. Since each adjacent element differs by atmost 1, we can observe that we have to go from element r to l and in each step we can either remain at same value or increase by one or decrease by one, with the condition that new value should be present in array A. The only way to reach l is through l + 1(since r occurs before l in array), which can’t be achieved since there is no such value in the array A.

Pseudo code:

```
A = []
scan(T)
for test = 0 to T - 1:
ans = "YES"
scan(N)
for i = 0 to N - 1:
scan(A[i])
sort(A)
for i = 0 to N - 2:
if A[i + 1] - A[i] > 1:
ans = "NO"
print ans
```

### COMPLEXITY:

================

O(N \text{log} N), since we sort array A.