Problem Description

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 Format

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 Format

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

6 3
3 1 4 1 5 9
4 1
3 3
2 5

1
-1
2

Hint

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