Wstęp do programowania w C++

Bajtazar pracuje w firmie BAJ sprzedającej gry komputerowe. Firma BAJ współpracuje z wieloma firmami kurierskimi, które dostarczają sprzedawane gry klientom firmy BAJ. Bajtazar prowadzi kontrolę tego, jak przebiegała współpraca firmy BAJ z firmami kurierskimi. Ma on listę kolejno wysłanych paczek, wraz z informacją o tym, która firma kurierska dostarczyła którą paczkę. Interesuje go, czy któraś z firm kurierskich nie uzyskała niezasłużonej przewagi nad innymi firmami kurierskimi. Jeżeli w jakimś przedziale czasu określona firma kurierska dostarczyła więcej niż połowę wysłanych wówczas paczek, to powiemy, że firma ta dominowała w tym czasie. Bajtazar chce stwierdzić, czy w określonych przedziałach czasu jakieś firmy kurierskie dominowały, a jeśli tak, to które to były firmy. Pomóż Bajtazarowi! Napisz program, który będzie znajdował dominującą firmę lub stwierdzi, że żadna firma nie dominowała.

Wejście

Pierwszy wiersz standardowego wejścia zawiera dwie liczby całkowite n i m (1 ≤ n, m ≤ 500 000), oddzielone pojedynczym odstępem i oznaczające liczbę wysłanych przez firmę BAJ przesyłek oraz liczbę przedziałów czasowych, dla których chcemy poznać dominujące firmy. Firmy kurierskie są ponumerowane od 1 do n. Drugi wiersz wejścia zawiera n liczb całkowitych p1, p2, . . . , pn (1 ≤ pi ≤ n), pooddzielanych pojedynczymi odstępami; pi oznacza numer firmy kurierskiej, która dostarczyła i-tą (w kolejności chronologicznej) wysłaną paczkę. Kolejne m wierszy zawiera opisy kolejnych zapytań, po jednym w wierszu. Opis każdego zapytania składa się z dwóch liczb całkowitych a i b (1 ≤ a ≤ b ≤ n), oddzielonych pojedynczym odstępem, oznaczających, że szukamy firmy dominującej w okresie między wysłaniem a-tej a b-tej paczki włącznie. W testach wartych łącznie 65% punktów zachodzi dodatkowy warunek n, m ≤ 50 000, a w testach wartych 30% punktów zachodzi n, m ≤ 5000.

Wyjście

Standardowe wyjście powinno zawierać m wierszy, w których powinny znaleźć się odpowiedzi na kolejne zapytania, po jednej w wierszu. W każdym wierszu powinna znaleźć się jedna liczba całkowita, równa numerowi firmy, która zdominowała rynek w rozważanym przedziale czasu, lub 0, jeśli takiej firmy nie było.

Dla danych wejściowych:
7 5
1 1 3 2 3 4 3
1 3
1 4
3 7
1 7
6 6
poprawnym wynikiem jest:
1
0
3
0
4