Sorting Algorithm

Nirjhor Father Timm Memorial Prog...
Limits 2s, 512 MB

Given an array AA with NN elements that is sorted in non-decreasing order. You will be given QQ queries. In each query, you will be given a range [L,R][L,R]. For each query, you have to find the number of non-negative integers XX such that X<220X < 2^{20} and after doing the following operation the whole array remains sorted (in non-decreasing order):

  • For each ii such that LiRL\leq i\leq R, assign Ai:=AiXA_i := A_i \oplus X.

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

Input starts with an integer T (1T105)T~(1\leq T\leq 10^5), denoting the number of test cases.

Each case starts with an integer N (1N105)N~(1\leq N\leq 10^5), denoting the number of elements in the array AA. The next line will contain NN integers separated by spaces which denote the elements of the array (1Ai<220)(1\leq A_i<2^{20}). It is guaranteed that the array is sorted, that is, AiAi+1A_i\leq A_{i+1} for all 1i<N1\leq i < N.

The next line contains an integer Q (1Q105)Q~(1\leq Q\leq 10^5) which denotes the number of queries. Each of the next QQ lines contains two space separated integer denoting LL and RR (LR)(L\leq R).

It is further guaranteed that the sum of NN over all test cases will not exceed 10510^5, and that the sum of QQ over all test cases will not exceed 10510^5.

Output

For each query, you have to print a line containing the number of such XX.

Sample

InputOutput
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 XX: 0,10, 1.

  • For X=0X = 0, the array becomes A=[1,4,5,5]A = [1, 4, 5, 5] if the operation is performed.

  • For X=1X = 1, the array becomes A=[0,5,5,5]A = [0, 5, 5, 5] if the operation is performed.

In the second query there are two values for XX: 0,60, 6.

  • For X=0X = 0, the array becomes A=[1,4,5,5]A = [1, 4, 5, 5] if the operation is performed.

  • For X=6X = 6, the array becomes A=[1,2,3,5]A = [1, 2, 3, 5] if the operation is performed.

Bitwise XOR. The bitwise XOR of non-negative integers AA and BB, denoted ABA\oplus B, is defined as follows:

  • When ABA\oplus B is written in base two, the kk-th digit from the right (k0)(k\geq 0) is 11 if and only if exactly one of the digits in that place of AA and BB is 11, and 00 otherwise.

For example, we have 35=63\oplus 5=6 (in base two: 011101=110011\oplus 101=110).


Submit

Login to submit.

Statistics

100% Solution Ratio
Soumya1Earliest, 3w ago
tasmeemrezaFastest, 0.1s
Soumya1Lightest, 5.7 MB
tasmeemrezaShortest, 1454B
Toph uses cookies. By continuing you agree to our Cookie Policy.