---
title: Sort
---

You are given an array $x_1,x_2,\dots,x_n$ of $n$ integers. Your task is to answer $q$ queries $(a, b)$. In one operation, you are allowed to do one of the following:
- sort the first $a$ numbers in nondecreasing order, or
- sort the last $b$ numbers in nondecreasing order.

What is the minimum number of operations needed to sort the whole array in nondecreasing order? In each query, the array starts from the initial values $x_1,x_2,\dots,x_n$.

# Input

The first line contains two integers $n$ and $q$: the length of the array and the number of queries.

The second line contains $n$ integers $x_1,x_2,\dots,x_n$: the contents of the array.

The next $q$ lines describe the queries. Each line contains two integers $a$ and $b$.

# Output

Print $q$ lines with the answers to each query. If it is impossible to sort the array, print "`-1`".

# Constraints

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

# Example

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

Output:
```
1
-1
2
```

_Explanation_: In the first query, the array can be sorted in one operation by sorting the first $4$ numbers.

The array cannot be sorted with the available operations in the second query.

In the third query, the array can be sorted in two operations: start by sorting the first $2$ numbers and then sort the last $5$ numbers.

# Scoring

| Subtask | Constraints | Points    |
| :-----: | ----------- | :-------: |
| 1       | $n,q\le 10$ and $a+b\le n$ in all queries | [score=1] |
| 2       | $n,q \le 10$ | [score=2] |
| 3       | $a+b \le n$ in all queries | [score=3] |
| 4       | $1 \le x_i \le 2$ | [score=4] |
| 5       | $n,q \le 5000$ and the array is a permutation of the numbers $1,2,\dots,n$ | [score=5] |
| 6       | $n,q \le 5000$ | [score=6] |
| 7       | No additional constraints | [score=7] |
