Thanos's sorting algorithm refers to the following procedure:
You have an array \(a[1], a[2], \dots, a[N]\) of length \(N\). You are also given \(Q\) queries, each with numbers \(l\) and \(r\). Your task is to find the minimum number of times the infinity stones must be used to sort the subarray \(a[l], a[l+1], \dots, a[r]\). It is guaranteed that the length of the given subarray is a power of two.
*In non-decreasing order, every element must be no smaller than the one before it. That is, \(a[1] \le a[2] \le \ldots \le a[N]\).
The first line contains \(N\) and \(Q\) – the number of elements and queries.
The second line contains \(a[1], a[2], \dots, a[N]\) – the array elements.
The next \(Q\) lines each contain \(l\) and \(r\) – the queries.
Print the answer for each query on its own line – \(Q\) lines in total.
For example, let \(N = 9\), \(a = [3, 1, 4, 1, 5, 9, 2, 6, 5]\) and \(Q = 3\).
In the first query \(l = 1\) and \(r = 8\), i.e. we want the minimum number of operations for the array \(a' = [3, 1, 4, 1, 5, 9, 2, 6]\). In the first operation we erase the left half of the array, giving \(a' = [5, 9, 2, 6]\). Suppose in the second operation we erase the right half. Then \(a' = [5, 9]\), which is sorted in non-decreasing order. Since we used 2 operations, the answer is \(2\).
In the second query \(l = 5\) and \(r = 5\). Since the array \(a' = [5]\) is already sorted, no operations are needed.
9 3 3 1 4 1 5 9 2 6 5 1 8 5 5 3 4
2 0 1