---
title: Rikiavimas
---

Duotas $n$ sveikųjų skaičių $x_1,x_2,\dots,x_n$ sąrašas. Jums reikia atsakyti į $q$ užklausų $(a, b)$. Vienos operacijos metu jūs galite atlikti vieną šių veiksmų:
- išrikiuoti pirmus $a$ skaičių nemažėjimo tvarka, arba
- išrikiuoti paskutinius $b$ skaičių nemažėjimo tvarka.

Kiekvienai užklausai jums reikia rasti mažiausią operacijų skaičių, reikalingą išrikiuoti sąrašą nemažėjimo tvarka. Apdorodami kiekvieną užklausą naudokite pradinį sąrašą $x_1,x_2,\dots,x_n$.

# Pradiniai duomenys

Pirmoje eilutėje pateikti du sveikieji skaičiai $n$ ir $q$ – skaičių sąrašo ilgis ir užklausų skaičius.

Antroje eilutėje pateikta $n$ sveikųjų skaičių $x_1,x_2,\dots,x_n$ – sąrašo elementai.

Kitose $q$ eilučių duotos užklausos. Kiekvienoje eilutėje pateikti du sveikieji skaičiai $a$ ir $b$.

# Išvestis

Išveskite $q$ eilučių – atsakymus į kiekvieną užklausą. Jei išrikiuoti masyvo neįmanoma, išveskite "`-1`".

# Ribojimai

- $1 \le n,q \le 2 \cdot 10^5$
- $1 \le x_i \le 10^9$
- $1 \le a,b \le n$ visose užklausose

# Pavyzdys

Pradiniai duomenys:
```
6 3
3 1 4 1 5 9
4 1
3 3
2 5
```

Išvestis:
```
1
-1
2
```

_Paaiškinimas_: Pirmoje užklausoje sąrašą galima išrikiuoti panaudojant vieną operaciją – išrikiuoti pirmus $4$ elementus.

Antroje užklausoje neįmanoma išrikiuoti sąrašo naudojant duotas operacijas.

Trečioje užklausoje sąrašą galima išrikiuoti panaudojus dvi operacijas: pirma išrikiuoti pirmus $2$ elementus ir tada išrikiuoti paskutinius $5$ elementus.

# Vertinimas

| Dalinė užduotis | Ribojimai | Taškai    |
| :-----: | ----------- | :-------: |
| 1       | $n,q\le 10$ ir $a+b\le n$ visose užklausose | [score=1] |
| 2       | $n,q \le 10$ | [score=2] |
| 3       | $a+b \le n$ visose užklausose | [score=3] |
| 4       | $1 \le x_i \le 2$ | [score=4] |
| 5       | $n,q \le 5000$ ir sąrašas yra skaičių $1,2,\dots,n$ keitinys | [score=5] |
| 6       | $n,q \le 5000$ | [score=6] |
| 7       | Papildomų ribojimų nėra | [score=7] |
