# PROBLEM LINK:

Practice

Contest: Division 1

Contest: Division 2

Contest: Division 3

Contest: Division 4

* Author:* pols_agyi_pols

*kingmessi*

**Tester:***iceknight1093*

**Editorialist:**# DIFFICULTY:

TBD

# PREREQUISITES:

None

# PROBLEM:

You’re given a permutation P.

Find the minimum integer K such that it’s possible to sort P by performing the following operation:

Choose indices i and j such that P_i + P_j \leq K, and swap the values of P_i and P_j.

# EXPLANATION:

Let’s fix a value of K and analyze when P can be sorted.

Note that P is a permutation, so when it’s sorted, the value at index i will itself be i.

If P_i \geq K, then no matter which index j is chosen, we’ll have P_i + P_j \gt K.

This means it’s not possible to move P_i at all - so if P_i \neq i it’s definitely impossible to sort P.

So, let’s assume P_i = i for all i \geq K.

That means the elements K, K+1, K+2, \ldots, N are already in place - we only need to worry about elements \lt K (which are all at positions \lt K as well).

It is, in fact, always possible to sort all these small elements.

The trick here is that the element 1 can be swapped with anything else, since its sum with any element \lt K cannot exceed K.

That gives us the following sorting algorithm:

- Move 1 to index K-1, then swap it with the element K-1 to obtain P_{K-1} = K-1.
- Move 1 to index K-2, then swap it with the element K-2 to obtain P_{K-2} = K-2.

\vdots - Move 1 to index 2, then swap it with the element 2 to obtain P_2 = 2.

After this, all the other elements are in place, so P_1 = 1 will also be true.

We now have a way to check if a specific value of K allows P to be sorted: simply check if all elements \geq K are in their respective final places.

To find the *minimum* possible value of K, we simply extend this idea a bit: we only need to find the largest suffix that’s already in place, which is easy to do with a linear scan.

If the elements N, N-1, N-2, \ldots, K are in place, but K-1 is not, the answer is K.

Alternately, since our check for a fixed K runs in linear time, you can use binary search to find the minimum K.

# TIME COMPLEXITY:

\mathcal{O}(N) per testcase.

# CODE:

## Editorialist's code (Python)

```
for _ in range(int(input())):
n = int(input())
p = list(map(int, input().split()))
ans = 0
for i in reversed(range(1, n+1)):
if p[i-1] != i:
ans = i+1
break
print(ans)
```