Profesor Joy, czołowy badacz historii kraju IOI, otrzymał dziennik, który podobno został napisany przez mieszkańca starożytnego IOI. Aby zbadać ówczesne życie na podstawie dziennika, postanowił przeanalizować opisane w nim wydarzenia.

Dziennik opisuje wydarzenia z $N$ dni, po jednym wydarzeniu dziennie. Wydarzenia podzielono na kilka typów. Typ wydarzenia z dnia $i$ ($1 \le i \le N$) jest reprezentowany przez liczbę całkowitą $X_i$. Im większa wartość $X_i$, tym większą skalę przypisuje się wydarzeniu.

Profesor Joy postanowił analizować dziennik w następujący sposób:

1. Wybrać pewien spójny okres spośród $N$ dni dziennika.
2. Zdefiniować ważność typu wydarzenia $t$ jako $t$ pomnożone przez liczbę wydarzeń typu $t$ w wybranym okresie.
3. Obliczyć ważność każdego typu wydarzenia i znaleźć największą z tych wartości.

Profesor Joy zlecił ci napisanie programu do analizy. Program ma znajdować największą ważność dla zadanego okresu.

Zadanie

Dane są typy wydarzeń z $N$ dni dziennika oraz $Q$ zapytań opisujących okresy. Napisz program, który dla każdego zapytania obliczy największą ważność typu wydarzenia.

Wejście

Wczytaj następujące dane ze standardowego wejścia.

• Pierwszy wiersz zawiera dwie liczby całkowite $N,Q$, oddzielone spacją. Oznaczają one, że dziennik obejmuje $N$ dni i podano $Q$ zapytań.
• Następny wiersz zawiera $N$ liczb całkowitych $X_1,\ldots,X_N$, oddzielonych spacjami. $X_i$ ($1 \le i \le N$) oznacza typ wydarzenia z dnia $i$.
• Wiersz $j$ ($1 \le j \le Q$) z następnych $Q$ wierszy zawiera liczby całkowite $A_j,B_j$ ($1 \le A_j \le B_j \le N$), oddzielone spacją. Zapytanie $j$ dotyczy okresu od dnia $A_j$ do dnia $B_j$.

Wyjście

Wypisz $Q$ wierszy na standardowe wyjście. W wierszu $j$ ($1 \le j \le Q$) wypisz liczbę całkowitą oznaczającą największą ważność dla zapytania $j$.

Ograniczenia

Wszystkie dane wejściowe spełniają następujące warunki.

• $1 \le N \le 100\,000$.
• $1 \le Q \le 100\,000$.
• $1 \le X_i \le 1\,000\,000\,000$ ($1 \le i \le N$).

Podzadania

Podzadanie 1 [5 punktów]

Spełnione są następujące warunki.

• $N \le 100$.
• $Q \le 100$.

Podzadanie 2 [10 punktów]

Spełnione są następujące warunki.

• $N \le 5\,000$.
• $Q \le 5\,000$.

Podzadanie 3 [25 punktów]

• Nie istnieją $i,j$ ($1 \le i \le Q$, $1 \le j \le Q$, $i \ne j$) takie, że $A_i \le A_j \le B_j \le B_i$.

Podzadanie 4 [60 punktów]

Brak dodatkowych ograniczeń.

Przykład

Wejście 1

5 5
9 8 7 8 9
1 2
3 4
4 4
1 4
2 4

Wyjście 1

9
8
8
16
16

Uwagi

• Dziennik obejmuje 5 dni, a opisane wydarzenia mają typ $7$, $8$ lub $9$.
• W okresie od dnia $1$ do dnia $2$ ważność typu $7$ wynosi $7 \times 0=0$, typu $8$ wynosi $8 \times 1=8$, a typu $9$ wynosi $9 \times 1=9$. Największa z tych wartości to $9$.
• W okresie od dnia $3$ do dnia $4$ ważność typu $7$ wynosi $7 \times 1=7$, typu $8$ wynosi $8 \times 1=8$, a typu $9$ wynosi $9 \times 0=0$. Największa z tych wartości to $8$.
• W dniu $4$ ważność typu $7$ wynosi $7 \times 0=0$, typu $8$ wynosi $8 \times 1=8$, a typu $9$ wynosi $9 \times 0=0$. Największa z tych wartości to $8$.
• W okresie od dnia $1$ do dnia $4$ ważność typu $7$ wynosi $7 \times 1=7$, typu $8$ wynosi $8 \times 2=16$, a typu $9$ wynosi $9 \times 1=9$. Największa z tych wartości to $16$.
• W okresie od dnia $2$ do dnia $4$ ważność typu $7$ wynosi $7 \times 1=7$, typu $8$ wynosi $8 \times 2=16$, a typu $9$ wynosi $9 \times 0=0$. Największa z tych wartości to $16$.

Wejście 2

8 4
9 9 19 9 9 15 9 19
1 4
4 6
3 5
5 8

Wyjście 2

27
18
19
19

Uwagi

Ten przykład spełnia ograniczenia podzadania 3.

Wejście 3

12 15
15 9 3 15 9 3 3 8 16 9 3 17
2 7
2 5
2 2
1 12
4 12
3 6
11 12
1 7
2 6
3 5
3 10
7 10
1 4
4 8
4 8

Wyjście 3

18
18
9
30
18
15
17
30
18
15
18
16
30
15
15