[ol2] XOR mutacije 2

Xor mutácie - st

Perica sa ocitol vo veľmi nepríjemnej situácii. Od svojho profesora dostal postupnosť kladných celých čísel
A₁, A₂, …, Aₙ dĺžky N. Keďže každý má svoje preferencie pri bitových operáciách, Pericov profesor uprednostňuje bitovú operáciu and pred operáciou xor, čo je pomerne zriedkavé. Aby Perica profesorovi vyhovel, daruje mu jednu dobrú postupnosť čísel. Postupnosť
S₁, S₂, …, Sₘ je dobrá, ak pre každú dvojicu indexov (i, j), kde 1 ≤ i ≤ j ≤ M, platí: Sᵢ and Sⱼ > Sᵢ xor Sⱼ Pomôžte Pericovi odpovedať na Q dopytov. V každom dopyte je daná podpostupnosť
A_L, A_{L+1}, …, A_R pôvodnej postupnosti. Odpoveďou je dĺžka najdlhšej dobrej podsekvencie tejto podpostupnosti. Presnejšie, treba nájsť najväčšie K, pre ktoré existujú indexy
L ≤ i₁ < i₂ < … < i_K ≤ R tak, že postupnosť
A_{i₁}, A_{i₂}, …, A_{i_K} je dobrá.

Popis vstupu V prvom riadku štandardného vstupu sú dve celé čísla N a Q – počet prvkov postupnosti a počet dopytov. V druhom riadku je N celých čísel Aᵢ – prvky postupnosti A. V nasledujúcich Q riadkoch sú po dve celé čísla L a R, ktoré určujú podpostupnosť
A_L, A_{L+1}, …, A_R.

Popis výstupu Vypíšte Q riadkov. V i-tom riadku má byť odpoveď na i-ty dopyt.

Príklad 1 Vstup 5 3 1 2 1 3 2 1 5 1 4 2 3 Výstup 3 2 1

Vysvetlenie V prvom dopyte je najdlhšia dobrá postupnosť (2, 3, 2). Platí totiž
2 and 2 > 2 xor 2,
2 and 3 > 2 xor 3 a
3 and 3 > 3 xor 3,
preto je táto postupnosť dobrá.
V druhom dopyte je najdlhšia dobrá postupnosť (2, 3) a v treťom (2).

Obmedzenia • 1 ≤ N, Q ≤ 5 · 10⁵ • 1 ≤ Aᵢ ≤ 10⁹ • 1 ≤ L ≤ R ≤ N Testy sú rozdelené do 6 skupín: • 10 bodov: N, Q ≤ 10 • 15 bodov: Aᵢ ≤ 8 • 20 bodov: všetky prvky sú mocniny dvojky, t. j. Aᵢ = 2^(Bᵢ) • 20 bodov: N, Q ≤ 5000 • 15 bodov: N, Q ≤ 10⁵ • 20 bodov: bez ďalších obmedzení

Poznámka Operátor exkluzívnej disjunkcie v Pascale je xor, v C++ sa zapisuje symbolom ^.
Operácia x xor y pre nezáporné celé čísla x, y sa definuje takto: čísla sa zapíšu v binárnom tvare, doplnia sa úvodné nuly na rovnakú dĺžku a potom pre každý bit platí: • 0,0 → 0 • 0,1 → 1 • 1,0 → 1 • 1,1 → 0 Výsledné bity tvoria binárny zápis čísla x xor y. Operátor konjunkcie v Pascale je and, v C++ sa zapisuje symbolom &.
Operácia x and y sa určí podobne, pričom pre každý bit platí: • 0,0 → 0 • 0,1 → 0 • 1,0 → 0 • 1,1 → 1 Výsledné bity tvoria binárny zápis čísla x and y.