Watson asks Does Permutation Exist

You need to reorder the array into some permutation B such that for every i:

∣Bi-Bi+1∣≤1

We must decide if such a permutation exists.

Key Insight

If we sort the array to get C (non-decreasing order):

• In the sorted array, adjacent numbers are as close as possible.

• Any other permutation can only make some adjacent differences bigger, never smaller.

So:

• If the sorted array already has some adjacent pair with difference > 1,
  then no permutation can satisfy the condition.

• If the sorted array has all adjacent differences ≤ 1, then the sorted array itself is a valid permutation.

Therefore, the check is simple:

1. Sort the array.

2. Check all adjacent pairs:

• If for any i, C[i+1] - C[i] > 1 → print NO.

• Otherwise → print YES.

Algorithm

For each test case:

1. Read N and array A.

2. Sort A.

3. For i from 0 to N-2:

• If A[i+1] - A[i] > 1:

• Print NO and stop checking this test.

4. If loop finishes without violation, print YES.

Time complexity per test: O(N log N) for sorting.
Given total N over tests ≤ 2 * 105, this is efficient.

Example

Sample 1:

1. A = [3, 2, 2, 3]
   Sorted: [2, 2, 3, 3]
   Differences: 0, 1, 0 → all ≤ 1 → YES.

2. A = [1, 5]
   Sorted: [1, 5]
   Difference: 4 > 1 → NO.

Pseudocode:

Java code

C code

C++ code

Python code

JavaScript code