You are given an array of \(N\) positive integers and \(Q\) queries. In each query, you are given two integers \(l\) and \(r\).
For each query, find the length of the longest subarray such that the bitwise \(AND\) of the subarray is \(2^k\) where \(l \leq k \leq r\) and if no subarray exists, then the answer will be \(0\).
Input format
- The first line contains \(T\) denoting the number of test cases. The description of each test case is as follows.
- The first line contains an integer \(N\) denoting the number of array elements.
- The next line contains \(N\) space-separated integers.
- The next line contains an integer \(Q\) denoting the number of queries that are required to be performed.
- Each of the next \(Q\) lines contains two integers \(l\) and \(r\).
Output format
For each test case, \(Q\) lines must be printed and the \(i^{th}\) line should contain the output for the \(i^{th}\) query.
Constraints
\(1 \leq T \leq 20\)
\(1 \leq N, Q \leq 5 * 10^5\)
\(1 \leq A_i \leq 10^{18}\)
\(0 \leq l \leq r \leq 60\)
- For the first query we can choose subarray \([0, 2]\).
- For the next query we can choose subarray \([3, 3]\).
Please login to use the editor
You need to be logged in to access the code editor
Loading...
Please wait while we load the editor
Login to unlock the editorial
Please login to use the editor
You need to be logged in to access the code editor
Loading...
Please wait while we load the editor