---
title: Сортування
---

Дано масив $x_1,x_2,\dots,x_n$ з $n$ цілих чисел. Ваше завдання — відповісти на $q$ запитів $(a, b)$. За одну операцію дозволяється виконати одну з наступних дій:
- відсортувати перші $a$ елементів у неспадаючому порядку, або
- відсортувати останні $b$ елементів у неспадаючому порядку.

Яка мінімальна кількість операцій потрібна, щоб відсортувати весь масив у неспадаючому порядку? У кожному запиті масив починається з початкових значень $x_1,x_2,\dots,x_n$.

# Вхідні дані

Перший рядок містить два цілих числа $n$ та $q$: довжину масиву та кількість запитів.

Другий рядок містить $n$ цілих чисел $x_1,x_2,\dots,x_n$: елементи масиву.

Наступні $q$ рядків описують запити. Кожен рядок містить два цілих числа $a$ та $b$.

# Вихідні дані

Виведіть $q$ рядків з відповідями на кожен запит. Якщо відсортувати масив неможливо, виведіть "`-1`".

# Обмеження

- $1 \le n,q \le 2 \cdot 10^5$
- $1 \le x_i \le 10^9$
- $1 \le a,b \le n$ у всіх запитах

# Приклад

Вхідні дані:
```
6 3
3 1 4 1 5 9
4 1
3 3
2 5
```

Вихідні дані:
```
1
-1
2
```

_Пояснення_: У першому запиті масив можна відсортувати за одну операцію, відсортувавши перші $4$ елементи.

У другому запиті відсортувати масив за допомогою доступних операцій неможливо.

У третьому запиті масив можна відсортувати за дві операції: спочатку відсортувати перші $2$ елементи, а потім відсортувати останні $5$ елементів.

# Оцінювання

| Підзадача | Обмеження | Бали    |
| :-------: | --------- | :-----: |
| 1         | $n,q\le 10$ та $a+b\le n$ у всіх запитах | [score=1] |
| 2         | $n,q \le 10$ | [score=2] |
| 3         | $a+b \le n$ у всіх запитах | [score=3] |
| 4         | $1 \le x_i \le 2$ | [score=4] |
| 5         | $n,q \le 5000$ та масив є перестановкою чисел $1,2,\dots,n$ | [score=5] |
| 6         | $n,q \le 5000$ | [score=6] |
| 7         | Без додаткових обмежень | [score=7] |
