#P12430. [BalticOI 2025] Exponents

[BalticOI 2025] Exponents

题目描述

The famous polymath Nicolaus Copernicus was born and grew up in Toruń in the 15th century. Archaeologists have recently discovered his notebook, and learned that he was fond of using powers of two to store large numbers. In particular, even when he added two powers of two:

2a+2b2^a + 2^b

Copernicus evaluated the result and then rounded up the result to the nearest power of two. That is, he would evaluate 2a+2b2^a + 2^b to 2max(a,b)+12^{\max(a,b)+1}. To evaluate a longer expression of the form:

2b1+2b2++2br2^{b_1}+2^{b_2}+\cdots + 2^{b_r}

he first inserted the brackets to make it well - parenthesised*. For example, an expression 25+24+24+24+252^5 + 2^4+2^4 + 2^4+2^5 can be made well - parenthesised to obtain ((25+24)+(24+(24+25)))((2^5 + 2^4)+(2^4+(2^4 + 2^5))). Finally, he evaluated the result of the obtained well - parenthesised expression, operating on powers of two as described above. Notice that the result might vary depending on how he inserts the brackets. For example, here are two possible ways to evaluate 25+24+24+24+252^5 + 2^4+2^4 + 2^4+2^5:

$((2^5 + 2^4)+(2^4 + 2^5))=((2^6+2^4)+2^5)=(2^7 + 2^6)=2^8$

$((2^5+(2^4 + 2^4))+(2^4 + 2^5))=((2^5 + 2^5)+2^6)=(2^6+2^6)=2^7$

The first page of the Copernicus' notebook contains only a single expression 2a1+2a2++2an2^{a_1}+2^{a_2}+\cdots + 2^{a_n} called the main expression. Later pages of the notebook then reference fragments of the main expression, which are of the form 2a+2a+1++2ar2^{a_\ell}+2^{a_{\ell + 1}}+\cdots + 2^{a_r}, for some 1rn1\leq \ell\leq r\leq n.

You are not sure what their meaning, but suspect that you should calculate, for each such fragment, the smallest possible result that can be obtained when evaluating the result as described above for the fragment. Note that each fragment is evaluated independently of the other fragments.

输入格式

The first line contains two integers nn and qq (1n,q3000001\leq n,q\leq300000) denoting the length of the main expression from the first page of the notebook and the number of queries, respectively.

The second line contains nn integers a1,a2,,ana_1,a_2,\cdots,a_n (0ai1090\leq a_i\leq 10^9), where the ii - th integer aia_i denotes the exponent of the ii - th power of two in the main expression.

The next qq lines describe the queries. Each query consists of two integers \ell and rr (1rn1\leq \ell\leq r\leq n) representing a fragment of the main expression starting at the \ell - th power of two and ending at the rr - th power of two.

输出格式

You should output qq lines. The ii - th line should contain the smallest possible result that can be obtained when evaluating the fragment described in the ii - th query. You should output only the exponent of the corresponding power of two.

8 4
2 4 2 5 4 4 4 5
4 8
1 4
2 5
1 7
7
7
7
8

提示

Subtasks Constrains Score
1 n8,q10n \leq 8, q \leq 10 6
2 n200n \leq 200 8
3 n,q2000n, q \leq 2000 23
4 ai20a_{i} \leq 20 22
5 No addition constrains 41