Count Ones in Binary Representation of Exponential Sum

Given a sequence \(a_1, a_2, \dots, a_n\) and \(m\) queries, each query asks for the number of ones in the binary representation of \(\sum_{i=l}^{r}2^{a_i}\). Due to the possibility of carries when summing powers of two, you cannot simply count the number of terms in the query. Instead, you must simulate the binary addition by repeatedly carrying over when a bit position has a value of 2 or more.

Note: The arithmetic may involve very large numbers; however, by using the frequency of exponents and managing the carries, you can compute the number of ones without computing the full sum.

inputFormat

The first line contains two integers \(n\) and \(m\) \( (1 \leq n, m \leq 10^5)\) denoting the length of the sequence and the number of queries respectively.

The second line contains \(n\) integers \(a_1, a_2, \dots, a_n\), where each \(a_i\) represents the exponent in the term \(2^{a_i}\).

Each of the next \(m\) lines contains two integers \(l\) and \(r\) \((1 \leq l \leq r \leq n)\) representing a query.

outputFormat

For each query, print a single integer, the number of ones in the binary representation of \(\sum_{i=l}^{r}2^{a_i}\).

sample

3 2
0 1 2
1 3
2 3

3
2