You are given an array of integers. Your task is to answer queries . In one operation, you are allowed to do one of the following:
sort the first numbers in nondecreasing order, or
sort the last 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 .
输入格式
The first line contains two integers and : the length of the array and the number of queries.
The second line contains integers : the contents of the array.
The next lines describe the queries. Each line contains two integers and .
输出格式
Print lines with the answers to each query. If it is impossible to sort the array, print "-1".
样例
样例输入 1
6 3
3 1 4 1 5 9
4 1
3 3
2 5
样例输出 1
1
-1
2
数据范围与提示
Explanation
In the first query, the array can be sorted in one operation by sorting the first 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 numbers and then sort the last numbers.
