P16362 [BalticOI 2026] 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$.

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$.

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

### 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. ### 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 ### Scoring | Subtask | Constraints | Points | | :-----: | ----------- | :-------: | | 1 | $n,q\le 10$ and $a+b\le n$ in all queries | $6$ | | 2 | $n,q \le 10$ | $5$ | | 3 | $a+b \le n$ in all queries | $7$ | | 4 | $1 \le x_i \le 2$ | $14$ | | 5 | $n,q \le 5000$ and the array is a permutation of the numbers $1,2,\dots,n$ | $23$ | | 6 | $n,q \le 5000$ | $12$ | | 7 | No additional constraints | $33$ |