[old] XOR mutacije 2

Перица се нашао у веома незгодној позицији. Oн је од свог професора добио низ позитивних целих бројева A_1, A_2, \cdots, A_N дужине N. Како свака особа има своје преференце по питању битовских операција, тако и Перичин професор више воли битовску операцију and у односу на операцију xor, што је веома ретка појава.

Како би Перица удовољио свом професору он ће му поклонити један добар низ бројева. Низ бројева S_1, S_2, \cdots, S_M је добар уколико за сваки пар бројева (i, j) \ (1 \leq i \leq j \leq M) важи S_i \ and \ S_j > S_i \ xor \ S_j.

Помозите Перици да одговори на Q упита, где је у сваком упиту дат подниз A_L, A_{L+1}, \cdots, A_R почетног низа, где је одговор на упит дужина најдуже добре подсеквенце тог подниза. Прецизније, потребно је наћи највеће K тако да постоји низ индекса L \leq i_1 < i_2 < \cdots < i_K \leq R такав да је низ A_{i_1}, A_{i_2}, \cdots, A_{i_K} добар.

Опис улаза

У првој линији стандарног улаза дата су два цела броја N и Q, број елемената низа и број упита редом.

У другој линији стандарног улаза дато је N целих бројева A_i, чланови низа A.

У наредних Q линија стандарног улаза дата су по два цела броја L и R, који означавају подниз A_L, A_{L+1}, \cdots, A_R.

Опис излаза

У Q линија стандарног излаза потребно је исписати решење за сваки упит. У i-тој линији се налази одговор на i-ти упит.

Пример 1

Улаз

5 3
1 2 1 3 2
1 5
1 4
2 3

Излаз

3
2
1

Објашњење

У првом упиту најдужи добар низ је (2, \ 3, \ 2). Како важи 2 \ and \ 2 > 2 \ xor \ 2, 2 \ and \ 3 > 2 \ xor \ 3 и 3 \ and \ 3 > 3 \ xor \ 3, тај низ је добар. У другом упиту најдужи добар низ је (2, \ 3), док је у трећем упиту најдужи добар низ (2).

Ограничења

• 1 \leq N, \ Q \leq 5 \cdot 10^5
• 1 \leq A_i \leq 10^9
• 1 \leq L \leq R \leq N

Тест примери су подељени у 6 дисјунктних група:

• У тестовима вредним 10 поена: N, Q \leq 10
• У тестовима вредним 15 поена: A_i \leq 8
• У тестовима вредним 20 поена: сви чланови низа A су степени двојке, тј. A_i = 2^{B_i} за неки низ B
• У тестовима вредним 20 поена: N, Q \leq 5000
• У тестовима вредним 15 поена: N, Q \leq 10^5
• У тестовима вредним 20 поена: без додатних ограничења.

Напомена

Оператор ексклузивне дисјункције у Pascal-u је означен са xor, док у C++ га записујемо помоћу симбола ^. Ова операција x\ \text{xor} \ y​ се за ненегативне целе бројеве x,y​ дефинише на следећи начин. Прво се бројеви запишу у бинарном запису. Уколико један број има мање цифара од другог, дописују му се водеће нуле све док не буду имали исти број бинарних цифара. Тако се добијају два низа бинарних цифара, означимо их са a_1, \ldots, a_k​ и b_1, \ldots b_k​. Затим се за сваку позицију i \in {1, \ldots, k }​ рачуна c_i​ помоћу следећих правила:

• За a_{i} = 0, b_{i} = 0 важи c_{i} = 0
• За a_{i} = 0, b_{i} = 1 важи c_{i} = 1
• За a_{i} = 1, b_{i} = 0 важи c_{i} = 1
• За a_{i} = 1, b_{i} = 1 важи c_{i} = 0

Низ бинарних цифара c_1, \ldots, c_k (који можда има водеће нуле) је бинарни запис резултата, односно броја x \ \text{xor} \ y.

Оператор конјункције у Pascal-u је означен са and, док у C++ га записујемо помоћу симбола &. Ова операција x\ \text{and} \ y​ се за ненегативне целе бројеве x,y​ дефинише на следећи начин. Прво се бројеви запишу у бинарном запису. Уколико један број има мање цифара од другог, дописују му се водеће нуле све док не буду имали исти број бинарних цифара. Тако се добијају два низа бинарних цифара, означимо их са a_1, \ldots, a_k​ и b_1, \ldots b_k​. Затим се за сваку позицију i \in \{1, \ldots, k \}​ рачуна c_i​ помоћу следећих правила:

• За a_{i} = 0, b_{i} = 0 важи c_{i} = 0
• За a_{i} = 0, b_{i} = 1 важи c_{i} = 0
• За a_{i} = 1, b_{i} = 0 важи c_{i} = 0
• За a_{i} = 1, b_{i} = 1 важи c_{i} = 1

Низ бинарних цифара c_1, \ldots, c_k (који можда има водеће нуле) је бинарни запис резултата, односно броја x \ \text{and} \ y.