---
title: Kārtošana
---

Jums ir dots masīvs $x_1,x_2,\dots,x_n$ ar $n$ veseliem skaitļiem. Jūsu uzdevums ir atbildēt uz $q$ vaicājumiem $(a, b)$. Vienā operācijā jums ir atļauts veikt vienu no sekojošām darbībām:
- sakārtot pirmos $a$ skaitļus nedilstošā secībā, or
- sakārtot pēdējos $b$ skaitļus nedilstošā secībā.

Kāds ir minimālais operāciju skaits, kas nepieciešams, lai sakārtotu visu masīvu nedilstošā secībā? Katrā vaicājumā masīvs sākas no sākotnējām vērtībām $x_1,x_2,\dots,x_n$.

# Ievaddati

Pirmajā rindā doti divi veseli skaitļi $n$ un $q$: masīva garums un vaicājumu skaits.

Otrajā rindā doti $n$ naturāli skaitļi $x_1,x_2,\dots,x_n$: masīva saturs.

Nākamās $q$ rindas apraksta vaicājumus. Katrā rindā ir divi veseli skaitļi $a$ un $b$.

# Izvaddati

Izdrukā $q$ rindas ar atbildi uz katru vaicājumu. Ja nav iespējams sakārtot masīvu, izdrukā "`-1`".

# Ierobežojumi

- $1 \le n,q \le 2 \cdot 10^5$
- $1 \le x_i \le 10^9$
- $1 \le a,b \le n$ visos vaicājumos

# Piemērs

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

Izvaddati:
```
1
-1
2
```


_Paskaidrojums_: Pirmajā vaicājumā masīvu var sakārtot vienā operācijā, sakārtojot pirmos $4$ skaitļus.

Masīvu nevar sakārtot, izmantojot pieejamās darbības otrajā vaicājumā.

Trešajā vaicājumā masīvu var sakārtot divās operācijās: vispirms sakārtot pirmos $2$ skaitļus un pēc tam sakārtot pēdējos $5$ skaitļus.

# Vērtēšana

| Apakšuzdevums | Ierobežojumi | Punkti    |
| :-----: | ----------- | :-------: |
| 1       | $n,q\le 10$ un $a+b\le n$ visos vaicājumos | [score=1] |
| 2       | $n,q \le 10$ | [score=2] |
| 3       | $a+b \le n$ visos vaicājumos | [score=3] |
| 4       | $1 \le x_i \le 2$ | [score=4] |
| 5       | $n,q \le 5000$ un masīvs ir skaitļu $1,2,\dots,n$ permutācija | [score=5] |
| 6       | $n,q \le 5000$ | [score=6] |
| 7       | Bez papildu ierobežojumiem| [score=7] |
