# Sorting Algorithm

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

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

• For each $i$ such that $L\leq i\leq R$, assign $A_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~(1\leq T\leq 10^5)$, denoting the number of test cases.

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

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

It is further guaranteed that the sum of $N$ over all test cases will not exceed $10^5$, and that the sum of $Q$ over all test cases will not exceed $10^5$.

## Output

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

## 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 $X$: $0, 1$.

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

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

In the second query there are two values for $X$: $0, 6$.

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

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

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

• When $A\oplus B$ is written in base two, the $k$-th digit from the right $(k\geq 0)$ is $1$ if and only if exactly one of the digits in that place of $A$ and $B$ is $1$, and $0$ otherwise.

For example, we have $3\oplus 5=6$ (in base two: $011\oplus 101=110$).

### Statistics

100% Solution Ratio
Soumya1Earliest, 3w ago
tasmeemrezaFastest, 0.1s
Soumya1Lightest, 5.7 MB
tasmeemrezaShortest, 1454B