# PROBLEM LINK:

Practice

Contest: Division 1

Contest: Division 2

Contest: Division 3

Contest: Division 4

* Author:* mexomerf

*yash_daga*

**Tester:***iceknight1093*

**Editorialist:**# DIFFICULTY:

TBD

# PREREQUISITES:

None

# PROBLEM:

You have an array A. Any two of its elements can be swapped, as long as they’re *not* adjacent.

Is it possible to sort A?

# EXPLANATION:

When N\geq 4, we have plenty of freedom - in fact, enough freedom that it’s always possible to sort the array!

## Proof

Let’s show that given any two indices i and j (i \lt j), we can swap the values of A_i and A_j without changing the rest of the array.

First, of course if i and j aren’t adjacent indices we can swap them directly; which means we only need to care about j = i+1.

Now,

- If i = 1, index 4 is not adjacent to either i or j.

So, perform the sequence: \text{swap}(A_1, A_4) \to \text{swap}(A_2, A_4) \to \text{swap}(A_1, A_4).

After these three moves, you can see that the values at positions 1 and 2 have swapped places, and everything else is as it was before. - If i \geq 3, index 1 is not adjacent to either i or j; so do the same as above.
- If i = 2, we have the following sequence of moves:

\text{swap}(A_2, A_4) \to \text{swap}(A_3, A_1) \to \text{swap}(A_1, A_4) \to \text{swap}(A_2, A_4) \to \text{swap}(A_1, A_3).

Once again, you can verify that this swaps the values at indices 2 and 3, with the others being unchanged.

That leaves us with N \leq 3.

- If N = 1, the array is already sorted.
- If N = 2, no swaps can be made - so the answer is
`Yes`

if A is already sorted and`No`

otherwise. - If N = 3, the middle element can’t be moved, but the first and last can be swapped if needed.

So, as long as \min(A_1, A_3) \leq A_2 \leq \max(A_1, A_3), it’s possible to sort the array; and otherwise it isn’t.

# TIME COMPLEXITY:

\mathcal{O}(N) per testcase.

# CODE:

## Editorialist's code (Python)

```
for _ in range(int(input())):
n = int(input())
a = list(map(int, input().split()))
if n == 2 and a[0] > a[1]: print('No')
elif n == 3:
a[0], a[2] = min(a[0], a[2]), max(a[0], a[2])
if a[0] <= a[1] <= a[2]: print('Yes')
else: print('No')
else:
print('Yes')
```