# PROBLEM LINK:

Practice

Contest: Division 1

Contest: Division 2

Contest: Division 3

Contest: Division 4

* Author:* iceknight1093

*sushil2006*

**Tester:***iceknight1093*

**Editorialist:**# DIFFICULTY:

Simple

# PREREQUISITES:

None

# PROBLEM:

You have an array A.

In one move, you can choose an odd-length subarray, and delete the leftmost occurrence of its median from it.

Find a sequence of operations that sorts A, or claim that this is impossible.

# EXPLANATION:

Let \text{mn} denote the minimum element of A.

Observe that no matter which subarray you operate on,

- If the median is \gt \text{mn}, obviously \text{mn} doesn’t get deleted from the array.
- If the median
*is*\text{mn}, then every element before the median (in sorted order) must also be equal to \text{mn}.

The length of the subarray being \gt 1 means that at least one such element exists.

So, even if one copy of \text{mn} gets deleted, A will still contain at least one more copy of \text{mn}.

This tells us that no matter how we perform the operations, at least one copy of \text{mn} will remain in A in the end.

In particular, since we delete the leftmost occurrence of A in a subarray, the *rightmost* occurrence of \text{mn} in A will never be deleted.

The exact same reasoning can be applied to the maximum element of A (call it \text{mx}).

That is, the rightmost occurrence of \text{mx} will not be deleted.

Let x be the largest index such that A_x = \text{mn}.

Let y be the largest index such that A_x = \text{mx}.

If x \gt y, then A can never be sorted - there will always be an occurrence of \text{mn} after \text{mx}.

On the other hand, if x \leq y, A can always be sorted.

The proof of this is in fact quite simple: **you can perform literally any sequence of operations!** (that reduces the array to length 2).

That is, while the array has length \gt 2, choose some subarray and operate on it.

This will reduce the length of the subarray by 1 - but as noted at the start, the rightmost occurrences of the minimum and maximum will remain.

So, when the array reaches length 2, the only remaining elements will be the rightmost occurrences of the minimum and maximum.

However, we’re in the case where the minimum appears before the maximum - so this 2-element array is certainly sorted!

# TIME COMPLEXITY:

\mathcal{O}(N) per testcase.

# CODE:

## Editorialist's code (PyPy3)

```
for _ in range(int(input())):
n = int(input())
a = list(map(int, input().split()))
last_mn = last_mx = 0
for i in range(1, n):
if a[i] >= a[last_mx]: last_mx = i
if a[i] <= a[last_mn]: last_mn = i
if last_mn > last_mx: print(-1)
else:
import random
print(n-2)
for i in range(n-2):
# make a random valid move since it does not matter
while True:
l, r = random.randint(1, n-i), random.randint(1, n-i)
if l == r or l%2 != r%2: continue
print(min(l, r), max(l, r))
break
```