Le professeur ジョイ, une sommité de la recherche sur l'histoire du pays IOI, a reçu un journal qui aurait été écrit par un habitant de ce pays dans l'Antiquité. Afin d'étudier la vie dans le pays IOI à cette époque à partir de ce journal, il a décidé d'examiner les événements qui y sont consignés.

Le journal rapporte les événements survenus pendant $N$ jours, à raison d'un événement par jour. Ces événements sont classés en plusieurs types. Le type de l'événement du jour $i$ ($1\le i\le N$) est représenté par un entier $X_i$. Plus la valeur de $X_i$ est grande, plus l'événement est considéré comme étant de grande ampleur.

Le professeur ジョイ a décidé d'analyser le journal de la manière suivante.

1. Choisir une période constituée de plusieurs jours consécutifs parmi les $N$ jours du journal.
2. Définir l'importance d'un type d'événement $t$ comme $t\times$ le nombre d'événements de type $t$ pendant cette période.
3. Calculer l'importance de chaque type d'événement et en déterminer la valeur maximale.

Le professeur ジョイ vous a chargé d'écrire un programme pour cette analyse. Ce programme doit pouvoir déterminer l'importance maximale lorsqu'on lui donne la période à analyser.

Tâche

Étant donnés les types d'événements des $N$ jours du journal et $Q$ requêtes décrivant des périodes du journal, écrivez un programme qui calcule, pour chaque requête, l'importance maximale d'un type d'événement.

Entrée

Lisez les données suivantes sur l'entrée standard.

• La première ligne contient les entiers $N,Q$, séparés par une espace. Ils indiquent que le journal couvre $N$ jours et que $Q$ requêtes sont données.
• La ligne suivante contient $N$ entiers $X_1,\ldots,X_N$, séparés par des espaces. $X_i$ ($1\le i\le N$) représente le type de l'événement du jour $i$.
• La $j$-ième des $Q$ lignes suivantes ($1\le j\le Q$) contient les entiers $A_j,B_j$ ($1\le A_j\le B_j\le N$), séparés par une espace. Ils indiquent que la $j$-ième requête porte sur la période allant du jour $A_j$ au jour $B_j$.

Sortie

Écrivez $Q$ lignes sur la sortie standard. Sur la $j$-ième ligne ($1\le j\le Q$), écrivez un entier représentant l'importance maximale pour la $j$-ième requête.

Contraintes

Toutes les données d'entrée satisfont les conditions suivantes.

• $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$).

Sous-tâches

Sous-tâche 1 [5 points]

Les conditions suivantes sont satisfaites.

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

Sous-tâche 2 [10 points]

Les conditions suivantes sont satisfaites.

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

Sous-tâche 3 [25 points]

• Il n'existe pas d'indices $i,j$ ($1\le i\le Q$, $1\le j\le Q$, $i\ne j$) tels que $A_i\le A_j\le B_j\le B_i$.

Sous-tâche 4 [60 points]

Aucune contrainte supplémentaire.

Exemples

Entrée 1

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

Sortie 1

9
8
8
16
16

Remarque

• Ce journal couvre 5 jours, et les types d'événements qu'il contient sont $7$, $8$ ou $9$.
• Du jour 1 au jour 2, les importances des types $7$, $8$ et $9$ sont respectivement $7\times 0=0$, $8\times 1=8$ et $9\times 1=9$. Leur maximum est donc $9$.
• Du jour 3 au jour 4, les importances des types $7$, $8$ et $9$ sont respectivement $7\times 1=7$, $8\times 1=8$ et $9\times 0=0$. Leur maximum est donc $8$.
• Au jour 4, les importances des types $7$, $8$ et $9$ sont respectivement $7\times 0=0$, $8\times 1=8$ et $9\times 0=0$. Leur maximum est donc $8$.
• Du jour 1 au jour 4, les importances des types $7$, $8$ et $9$ sont respectivement $7\times 1=7$, $8\times 2=16$ et $9\times 1=9$. Leur maximum est donc $16$.
• Du jour 2 au jour 4, les importances des types $7$, $8$ et $9$ sont respectivement $7\times 1=7$, $8\times 2=16$ et $9\times 0=0$. Leur maximum est donc $16$.

Entrée 2

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

Sortie 2

27
18
19
19

Remarque

Cette entrée satisfait les contraintes de la sous-tâche 3.

Entrée 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

Sortie 3

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