Given an array with elements that is sorted in non-decreasing order. You will be given queries. In each query, you will be given a range . For each query, you have to find the number of non-negative integers such that and after doing the following operation the whole array remains sorted (in non-decreasing order):
Note that the queries are independent. So you do not actually apply the operations on the array when you move on to the next query.
Input starts with an integer , denoting the number of test cases.
Each case starts with an integer , denoting the number of elements in the array . The next line will contain integers separated by spaces which denote the elements of the array . It is guaranteed that the array is sorted, that is, for all .
The next line contains an integer which denotes the number of queries. Each of the next lines contains two space separated integer denoting and .
It is further guaranteed that the sum of over all test cases will not exceed , and that the sum of over all test cases will not exceed .
For each query, you have to print a line containing the number of such .
Input | Output |
---|---|
1 4 1 4 5 5 3 1 2 2 3 1 4 | 2 2 262144 |
In the first query there are two values for : .
In the second query there are two values for : .
Bitwise XOR. The bitwise XOR of non-negative integers and , denoted , is defined as follows:
For example, we have (in base two: ). |