Mario has advanced further into the turtle kingdom. He is on his way towards saving the princess now. However, now the entire army has grouped against him.

The soldiers are standing in a straight line, and each of them may not have the same strength. Therefore, the strategy employed by Mario will heavily depend on the order in which the stronger soldiers appear in the line. Also he needs to find the ordering of the subsets inside the line of soldiers, so that he can change his strategy as he goes about defeating them.

An array of the strengths of n soldiers is given as a[0], a[1], a[2], ..., a[n-1].
For any input of the form "i j" , the output should be as follows:
If the subarray a[i], a[i+1], ... a[j] is unsorted, output 0.
If the subarray a[i], a[i+1], ... a[j] is sorted in non-descending order, output 1.
If the subarray a[i], a[i+1], ... a[j] is sorted in non-ascending order, output 2.
If the subarray a[i], a[i+1], ... a[j] is sorted in both non-ascending and non-descending order (i.e, if all the elements in the range are equal), output 3.

Input
The first line contains two space separated integers n and m. (1 <= n <= 1000000, 1 <= m <= 1000000)
The next lines contain the elements of the array. (-5000 <= a[i] <= 5000)
The next m lines contain the queries of the form i,j (0 <= i,j <= n)

Output
m lines, the result for the corresponding query.

Sample I/O

Input
15 6
-7 0 9 9 9 -1 -4 -8 -8 -9 -11 0 0 1 -1
0 5
2 4
11 12
1 4
2 5
1 1

Output
0
3
3
1
2
3