---
title: Sorteerimine
---

Sulle on antud täisarvude massiiv $x_1, x_2, \dots, x_n$. Sinu ülesandeks on vastata $q$ päringule $(a, b)$. Ühe operatsiooniga on lubatud teha järgnevat:
- sorteeri esimesed $a$ numbrit mittekahanevas järjekorras, või
- sorteeri viimased $b$ numbrit mittekahanevas järjekorras.

Mis on minimaalne arv operatsioone, mille abil on võimalik kogu massiiv mittekahanevas järjekorras sorteerida?
Iga päringu alguses on massiiv initsialiseeritud algväärtustega $x_1, x_2, \dots, x_n$.

# Sisend

Sisendi esimesel real on kaks täisarvu $n$ ja $q$: vastavalt massiivi pikkus ja päringute arv.

Teisel real on $n$ täisarvu $x_1, x_2, \dots, x_n$: massiivi sisu.

Järgnevad $q$ rida kirjeldavad päringuid. Igal real on kaks täisarvu $a$ ja $b$.

# Väljund

Väljasta $q$ rida: iga päringu vastused. Kui massiivi on võimatu sorteerida, siis väljasta "`-1`".

# Piirangud

- $1 \le n,q \le 2 \cdot 10^5$
- $1 \le x_i \le 10^9$
- igas päringus $1 \le a,b \le n$

# Näide

Sisend:
```
6 3
3 1 4 1 5 9
4 1
3 3
2 5
```

Väljund:
```
1
-1
2
```

_Selgitus_: Esimeses päringus on massiiv võimalik sorteerida ühe operatsiooniga, sorteerides esimesed $4$ arvu.

Teises päringus ei ole võimalik massiivi antud päringutega sorteerida.

Kolmandas päringus saab massiivi sorteerida kahe päringuga: esiteks sorteerida esimesed $2$ arvu ja teiseks viimased $5$ arvu.

# Hindamine

| Alamülesanne | Piirangud | Punkte    |
| :-----: | ----------- | :-------: |
| 1       | $n,q\le 10$ ja igas päringus $a+b\le n$ | [score=1] |
| 2       | $n,q \le 10$ | [score=2] |
| 3       | igas päringus $a+b \le n$ | [score=3] |
| 4       | $1 \le x_i \le 2$ | [score=4] |
| 5       | $n,q \le 5000$ ja massiv on arvude $1,2,\dots,n$ mingi permutatsioon | [score=5] |
| 6       | $n,q \le 5000$ | [score=6] |
| 7       | Lisapiirangud puuduvad | [score=7] |
