---
title: Sort
---

Dany jest ciąg $x_1, x_2,\dots,x_n$ złożony z $n$ liczb całkowitych. Twoim zadaniem jest
odpowiedzenie na $q$ zapytań $(a, b)$. W jednej operacji możesz zrobić jedną z rzeczy:
- posortuj pierwsze $a$ liczb niemalejąco lub
- posortuj ostatnie $b$ liczb niemalejąco.

Jaka jest minimalna liczba operacji potrzebnych żeby posortować cały ciąg niemalejąco? W każdym zapytaniu
ciąg zaczyna z początkowych wartości $x_1,x_2,\dots,x_n$.


# Wejście

Pierwszy wiersz wejścia zawiera dwie liczby całkowite $n$ i $q$: długość ciągu i liczbę zapytań.

Drugi wiersz zawiera $n$ liczb całkowitych $x_1,x_2,\dots,x_n$: wartości ciągu.

Następne $q$ wierszy opisuje zapytania. Każdy wiersz zawiera dwie liczby całkowite $a$ i $b$.

# Wyjście

Wypisz $q$ wierszy zawierających odpowiedzi na kolejne zapytania. Jeśli nie da się posortować
ciągu wypisz "`-1`".

# Ograniczenia

- $1 \le n,q \le 2 \cdot 10^5$
- $1 \le x_i \le 10^9$
- $1 \le a,b \le n$ we wszystkich zapytaniach

# Przykład

Wejście:
```
6 3
3 1 4 1 5 9
4 1
3 3
2 5
```

Wyjście:
```
1
-1
2
```

_Wyjaśnienie_: W pierwszym zapytaniu ciąg może być posortowany w jednej operacji sortując pierwsze $4$ liczby.

Ciąg nie może zostać posortowany przy użyciu dostępnych operacji w drugim zapytaniu.

W trzecim zapytaniu ciąg może zostać posortowany w dwóch operacjach: na początku sortując pierwsze $2$ liczby
a potem sortując ostatnie $5$.

# Ocenianie

| Podzadanie | Ograniczenia | Punkty    |
| :-----: | ----------- | :-------: |
| 1       | $n,q\le 10$ i $a+b\le n$ we wszystkich zapytaniach | [score=1] |
| 2       | $n,q \le 10$ | [score=2] |
| 3       | $a+b \le n$ we wszystkich zapytaniach | [score=3] |
| 4       | $1 \le x_i \le 2$ | [score=4] |
| 5       | $n,q \le 5000$ i ciąg jest permutacją liczb $1,2,\dots,n$ | [score=5] |
| 6       | $n,q \le 5000$ | [score=6] |
| 7       | Brak dodatkowych ograniczeń | [score=7] |
