---
title: Sortierung
---

Gegeben sei ein Array $x_1,x_2,\dots,x_n$ mit $n$ Ganzzahlen. Deine Aufgabe ist es, $q$ Abfragen $(a, b)$ zu beantworten. In einer Operation kannst du eine von zwei Dingen tun:
- die ersten $a$ Zahlen in nicht absteigender Reihenfolge sortieren, oder
- die letzten $b$ Zahlen in nicht absteigender Reihenfolge.

Wie viele Operationen brauchst du mindestens, um das ganze Array in nicht absteigender Reihenfolge zu sortieren? Für jede Abfrage sei das Array zu Beginn wieder $x_1,x_2,\dots,x_n$.

# Eingabe

Die erste Zeile enthält zwei Ganzzahlen $n$ und $q$: die Länge des Arrays und die Anzahl der Abfragen.

Die zweite Zeile enthält $n$ Ganzzahlen $x_1,x_2,\dots,x_n$: der Inhalt des Arrays.

Die nächsten $q$ Zeilen beschreiben die Abfragen. Jede dieser Zeilen enthält zwei Ganzzahlen $a$ und $b$.

# Ausgabe

Gib $q$ Zeilen mit den jeweiligen Antworten auf jede Abfrage aus. Wenn es nicht möglich ist, das Array zu sortieren, gib „`-1`“ aus.

# Beschränkungen

- $1 \le n,q \le 2 \cdot 10^5$
- $1 \le x_i \le 10^9$
- $1 \le a,b \le n$ in allen Abfragen

# Beispiel

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

Ausgabe:
```
1
-1
2
```

_Erklärung_: In der ersten Abfrage kann das Array mit einer einzigen Operation sortiert werden, in dem die ersten $4$ Zahlen sortiert werden.

Mit den in der zweiten Abfrage zu Verfügung stehenden Operationen kann das Array nicht sortiert werden.

In der dritten Abfrage kann das Array mit zwei Operationen sortiert werden, indem zuerst die ersten $2$ Zahlen und dann die letzten $5$ sortiert werden.

# Bewertung

| Teilaufgabe | Beschränkungen | Punkte    |
| :-----: | ----------- | :-------: |
| 1       | $n,q\le 10$ und $a+b\le n$ in allen Abfragen | [score=1] |
| 2       | $n,q \le 10$ | [score=2] |
| 3       | $a+b \le n$ in allen Abfragen | [score=3] |
| 4       | $1 \le x_i \le 2$ | [score=4] |
| 5       | $n,q \le 5000$ und das Array ist eine Permutation der Zahlen $1,2,\dots,n$ | [score=5] |
| 6       | $n,q \le 5000$ | [score=6] |
| 7       | Keine weiteren Beschränkungen | [score=7] |
