Maximizing Popcount Sum

You are given a sequence of non-negative integers \(a_1, a_2, \dots, a_n\) of length \(n\). You are then given \(q\) queries. Each query provides two non-negative integers \(L\) and \(R\) and asks you to compute

$$\max_{x=L}^{R} \left( \sum_{i=1}^{n} \mathrm{popcount}(a_i+x) \right), $$

where \(\mathrm{popcount}(x)\) is the number of ones in the binary representation of \(x\). For each query, output the maximum possible sum.

inputFormat

The first line contains an integer \(n\) denoting the number of elements in the sequence. The second line contains \(n\) non-negative integers \(a_1, a_2, \dots, a_n\). The third line contains an integer \(q\) representing the number of queries. Then \(q\) lines follow; each line contains two non-negative integers \(L\) and \(R\) separated by a space.

Note: It is guaranteed that the range \([L, R]\) is small enough to allow a brute-force solution.

outputFormat

For each query, output one line containing a single integer, which is the maximum value of \(\sum_{i=1}^{n} \mathrm{popcount}(a_i+x)\) for \(x\) in the range \([L, R]\).

sample

3
1 2 3
2
0 1
2 3

4
4

</p>