[old] XOR mutacije 2

Pistike egy nagyon kellemetlen helyzetbe került. A tanárától kapott egy N hosszúságú pozitív egész számokból álló sorozatot: A_1, A_2, \cdots, A_N. Mivel mindenkinek megvannak a saját preferenciái a bitműveletek terén, Pistike tanára az and bitműveletet jobban kedveli a xor műveletnél, ami meglehetősen ritka jelenség.

Annak érdekében, hogy Pistike a tanára kedvében járjon, ajándékba ad neki egy jó számsorozatot. Egy S_1, S_2, \cdots, S_M számsorozat akkor jó, ha minden (i, j) \ (1 \leq i \leq j \leq M) számpárra teljesül, hogy S_i \ and \ S_j > S_i \ xor \ S_j.

Segítsetek Pistikének abban, hogy meg tudjon válaszolni Q darab lekérdezést! Minden lekérdezésben adott az eredeti sorozat egy A_L, A_{L+1}, \cdots, A_R részsorozata, és a válasz a részsorozat leghosszabb jó részszekvenciájának hossza. Pontosabban, meg kell találni a legnagyobb K értéket, amelyre létezik olyan L \leq i_1 < i_2 < \cdots < i_K \leq R indexsorozat, amelynek esetén az A_{i_1}, A_{i_2}, \cdots, A_{i_K} sorozat jó.

A bemenet leírása

A szabványos bemenet első sorában két egész szám található: N és Q, amelyek rendre a sorozat elemeinek számát és a lekérdezések számát jelölik.

A szabványos bemenet második sorában N darab A_i egész szám található, amelyek az A sorozat elemei.

A következő Q sor mindegyikében két egész szám, L és R szerepel, amelyek az A_L, A_{L+1}, \cdots, A_R részsorozatot jelölik.

A kimenet leírása

A szabványos kimenet Q sorból kell hogy álljon, mivel minden lekérdezés válaszát kell hogy tartalmazza. Az i-edik sorban az i-edik lekérdezés válasza kell hogy megjelenjen.

1. példa

Bemenet

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

Kimenet

3
2
1

A példa magyarázata

Az első lekérdezésben a leghosszabb jó sorozat a (2, \ 3, \ 2). Mivel teljesül, hogy 2 \ and \ 2 > 2 \ xor \ 2, 2 \ and \ 3 > 2 \ xor \ 3 és 3 \ and \ 3 > 3 \ xor \ 3, ez a sorozat jó.

A második lekérdezésben a leghosszabb jó sorozat a (2, \ 3), míg a harmadikban a (2).

Korlátozások

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

A tesztpéldák hat diszjunkt csoportba vannak sorolva:

• A 10 pontot érő tesztpéldákban: N, Q \leq 10
• A 15 pontot érő tesztpéldákban: A_i \leq 8
• A 20 pontot érő tesztpéldákban: az A sorozat minden eleme a kettő hatványa, azaz A_i = 2^{B_i} valamely B sorozatra
• A 20 pontot érő tesztpéldákban: N, Q \leq 5000
• A 15 pontot érő tesztpéldákban: N, Q \leq 10^5
• A 20 pontot érő tesztpéldákban: nincsenek további korlátozások.

Megjegyzés

A kizáró vagy jelölésére Pascal-ban a xor-t használják, míg C++-ban a ^ szimbólummal írjuk le. Az x\ \text{xor} \ y műveletet az x,y nemnegatív számok esetén a folytatásban leírt módon definiálhatjuk. Először a számokat bináris formában kell felírni. Ha egy szám rövidebb, mint a másik, akkor azt vezető nullákkal kell kiegészíteni mindaddig, amig a bináris számjegyek száma nem lesz megegyező. Így a bináris számok két sorozatát kapjuk, amelyekre a_1, \ldots, a_k és b_1, \ldots b_k jelölést használjuk. Majd minden i \in {1, \ldots, k } pozícióra kiszámoljuk a c_i-t az alábbi szabályok mentén:

• Ha a_{i} = 0, b_{i} = 0, akkor c_{i} = 0
• Ha a_{i} = 0, b_{i} = 1 akkor c_{i} = 1
• Ha a_{i} = 1, b_{i} = 0 akkor c_{i} = 1
• Ha a_{i} = 1, b_{i} = 1 akkor c_{i} = 0

A c_1, \ldots, c_k bináris számjegyekből alkotott sorozat (amely tartalmazhat vezető nullákat is) az eredmény bináris leírása, vagyis az x \ \text{xor} \ y számé.

A konjunkció operátora a Pascal programozási nyelvben and-del van jelölve, míg a C++ programozási nyelvben az & szimbólummal. Az x\ \text{and} \ y művelet az x,y nemnegatív, egész számokra az alábbi módon definiálható: Először a számokat bináris alakban kell felírni. Ha egy szám rövidebb, mint a másik, akkor azt vezető nullákkal kell kiegészíteni mindaddig, amíg a bináris számjegyek száma nem lesz megegyező. Így a bináris számok két sorozatát kapjuk, amelyekre a_1, \ldots, a_k és b_1, \ldots b_k jelölést használjuk. Majd minden i \in \{1, \ldots, k \} pozícióra kiszámoljuk a c_i-t az alábbi szabályok mentén:

• Ha a_{i} = 0, b_{i} = 0, akkor c_{i} = 0
• Ha a_{i} = 0, b_{i} = 1, akkor c_{i} = 0
• Ha a_{i} = 1, b_{i} = 0, akkor c_{i} = 0
• Ha a_{i} = 1, b_{i} = 1, akkor c_{i} = 1

A c_1, \ldots, c_k bináris számjegyekből alkotott sorozat (amely tartalmazhat vezető nullákat is) az eredmény bináris leírása, vagyis az x \ \text{and} \ y számé.