---
title: Röðun
---

Þér er gefið fylki $x_1,x_2,\dots,x_n$ með $n$ heiltölum. Þitt verkefni er að svara $q$ fyrirspurnum $(a, b)$. Í einni aðgerð mátt þú gera eitt af eftirfarandi:
- raða fyrstu $a$ tölum í vaxandi röð, eða
- raða síðustu $b$ tölum í vaxandi röð

Hvað er minnsti fjöldi aðgerð sem þarf til að raða fylkinu? Í hverri fyrirspurn, byrjar fylkið í upphaflegri röðun $x_1,x_2,\dots,x_n$.

# Intak

Fyrsta lína inniheldur tvær heiltölur $n$ og $q$: stærð fylkis og fjölda fyrirspurna.

Önnur lína inniheldur $n$ heiltölur $x_1,x_2,\dots,x_n$: tölurnar í fylkinu.

Næstu $q$ línur lýsa fyrirspurnum. Hver lína inniheldur tvær heiltölur $a$ og $b$.

# Úttak

Prentið út $q$ línur með svör fyrir hverja fyrirspurn. Ef ekki er hægt að raða fylkið, prentið "`-1`".

# Takmarkanir

- $1 \le n,q \le 2 \cdot 10^5$
- $1 \le x_i \le 10^9$
- $1 \le a,b \le n$ í öllum fyrirspurnum

# Dæmi

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

Úttak:
```
1
-1
2
```

_Útskíring_: Í fyrstu fyrirspurn, getur fylkið verið raðað með einni aðgerð með því að raða fyrstu $4$ tölum.

Ekki er hægt að raða fylkið með gefnum aðgerðum í annari fyrirspurn.

Í þriðju fyrirspurn, getur fylkið verið raðað með tveimur aðgerðum: fyrst þarf að raða fyrstu $2$ tölum og svo síðustu $5$ tölum.

# Stigagjöf

| Hópur | Takmarkanir | Stig |
| :-----: | ----------- | :-------: |
| 1       | $n,q\le 10$ og $a+b\le n$ í öllum fyrirspurnum | [score=1] |
| 2       | $n,q \le 10$ | [score=2] |
| 3       | $a+b \le n$ í öllum fyrirspurnum | [score=3] |
| 4       | $1 \le x_i \le 2$ | [score=4] |
| 5       | $n,q \le 5000$ og fylkið er umröðun talana $1,2,\dots,n$ | [score=5] |
| 6       | $n,q \le 5000$ | [score=6] |
| 7       | Engar frekari takmarkanir | [score=7] |
