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