Problem description

Urząd miejski Wrocławia zatrudnił Cię w ramach projektu, którego celem jest rozwinięcie sztucznej inteligencji nowej generacji i zastosowanie jej do usprawnienia ruchu drogowego na terenie miasta. Twój przełożony napotkał jednak pewien problem – dane potrzebne do szkolenia tak potężnej inteligencji zajmują zbyt wiele miejsca. Zwrócił się do Ciebie, legendarnego hakjera, abyś, korzystając z najnowszych technik kodowania, zmniejszył rozmiar danych treningowych.

Kodowanie to funkcja f przyporządkowująca ciąg 0-1 dla każdego elementu występującego w danych wejściowych. Aby każdą wiadomość można było jednoznacznie odkodować, warunkiem koniecznym jest, żeby dla każej pary elementów l_i i l_j, ciąg f(l_i) nie był prefiksem f(l_j). Koszt kodowania f dla danych d₁, d₂, ..., d_N jest określany przez długość ciągu f(d₁)f(d₂)...f(d_N). Powierzone Tobie zadanie wymaga, aby koszt f był jak najmniejszy.

Nadal nie jest pewne, które części danych należy zakodować, dlatego Twój przełożony przygotował dla Ciebie Q potencjalnych przedziałów. Twoje zadanie sprowadza się do przetworzenia ciągu d₁, d₂, ..., d_N o długości N, który reprezentuje dane do trenowania, oraz udzielenia odpowiedzi na Q zapytań w postaci l_i r_i dotyczących potencjalnego kosztu kodowania na danym przedziale. Każde zapytanie rozpatrywane jest niezależnie od pozostałych.

Wejście

Pierwszy wiersz zawiera liczbę N. Drugi wiersz zawiera ciąg danych d_i o długości N. Kolejne Q wierszy zawiera opis zapytań. Każdy z tych wierszy zawiera dwie liczby l_i i r_i — pozycje lewego i prawego krańca przedziału. Pozycje są indeksowane od 1. Przedziały mogą się nakładać. To samo zapytanie może pojawić się wiele razy.

Wyjście

Wypisz dokładnie Q wierszy. Każdy z nich powinnien zawierać jedną liczbę — minimalną długość zakodowanego przedziału d_li, ..., d_ri

Ograniczenia

1 ≤ N ≤ 400 000, 1 ≤ Q ≤ 400 000, 1 ≤ d_i ≤ 400 000 1 ≤ l_i ≤ r_i ≤ N

Podzadania

Przykład

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

10
3
3
5
0