---
title: Järjestys
---

Annettuna on taulukko $x_1,x_2,\dots,x_n$, jossa on $n$ kokonaislukua. Tehtäväsi on antaa vastaus $q$ kyselyyn muotoa $(a, b)$. Joka operaatiossa voit tehdä jommankumman seuraavista:
- järjestä ensimmäiset $a$ lukua pienimmästä suurimpaan tai
- järjestä viimeiset $b$ lukua pienimmästä suurimpaan.

Mikä on pienin tarvittava määrä operaatioita, joiden avulla voidaan järjestää koko taulukko pienimmästä suurimpaan? Jokaisessa kyselyssä taulukon sisältönä on aluksi alkuarvot $x_1,x_2,\dots,x_n$.

# Syöte

Ensimmäisellä rivillä on kaksi kokonaislukua $n$ ja $q$: taulukon koko ja kyselyiden määrä.

Toisella rivillä on $n$ kokonaislukua $x_1,x_2,\dots,x_n$: taulukon sisältö.

Seuraavat $q$ riviä kuvaavat kyselyt. Jokaisella rivillä on kaksi kokonaislukua $a$ ja $b$.

# Tuloste

Tulosta $q$ riviä, joilla on kyselyjen vastaukset. Jos taulukkoa ei ole mahdollista järjestää, tulosta "`-1`".

# Rajat

- $1 \le n,q \le 2 \cdot 10^5$
- $1 \le x_i \le 10^9$
- $1 \le a,b \le n$ kaikissa kyselyissä

# Esimerkki

Syöte:
```
6 3
3 1 4 1 5 9
4 1
3 3
2 5
```

Tuloste:
```
1
-1
2
```

_Selitys_:  Ensimmäisessä kyselyssä taulukko voidaan järjestää yhdellä operaatiolla järjestämällä ensimmäiset $4$ lukua.

Toisessa kyselyssä taulukkoa ei voida järjestää saatavilla olevilla operaatioilla.

Kolmannessa kyselyssä taulukko voidaan järjestää kahdella operaatiolla järjestämällä ensimmäiset $2$ lukua ja sitten jälkimmäiset $5$ lukua.

# Pisteytys

| Osatehtävä | Rajoitukset | Pisteet    |
| :-----: | ----------- | :-------: |
| 1       | $n,q\le 10$ ja $a+b\le n$ kaikissa kyselyissä | [score=1] |
| 2       | $n,q \le 10$ | [score=2] |
| 3       | $a+b \le n$ kaikissa kyselyissä | [score=3] |
| 4       | $1 \le x_i \le 2$ | [score=4] |
| 5       | $n,q \le 5000$ ja taulukko on lukujen $1,2,\dots,n$ permutaatio | [score=5] |
| 6       | $n,q \le 5000$ | [score=6] |
| 7       | Ei lisärajoituksia | [score=7] |
