Професор Joy, провідний дослідник історії країни IOI, отримав щоденник, який, як вважають, написав мешканець стародавньої країни IOI. Щоб дослідити життя у стародавній країні IOI за цим щоденником, професор Joy вирішив вивчити описані в ньому події.

У щоденнику описано події за $N$ днів, по одній події на день. Події поділяються на кілька типів. Тип події в день $i$ ($1 \le i \le N$) позначається цілим числом $X_i$. Вважається, що чим більше значення $X_i$, тим масштабнішою була подія.

Професор Joy вирішив аналізувати щоденник так.

1. Вибрати кілька послідовних днів серед $N$ днів щоденника як період для аналізу.
2. Визначити важливість типу подій $t$ як $t\times(\text{кількість подій типу }t\text{ у цьому періоді})$.
3. Обчислити важливість усіх типів подій і знайти найбільше з цих значень.

Професор Joy доручив вам написати програму для аналізу. Вона має визначати найбільшу важливість для заданого періоду аналізу.

Завдання

За типами подій за $N$ днів щоденника та $Q$ запитами, що задають періоди в щоденнику, напишіть програму, яка для кожного запиту знаходить найбільшу важливість типу подій.

Вхідні дані

Прочитайте такі дані зі стандартного вводу.

• Перший рядок містить цілі числа $N,Q$, розділені пробілом. Це означає, що щоденник охоплює $N$ днів і задано $Q$ запитів.
• Наступний рядок містить $N$ цілих чисел $X_1,\ldots,X_N$, розділених пробілами. $X_i$ ($1 \le i \le N$) задає тип події в день $i$.
• Рядок $j$ ($1 \le j \le Q$) із наступних $Q$ рядків містить цілі числа $A_j,B_j$ ($1 \le A_j \le B_j \le N$), розділені пробілом. Це означає, що запит $j$ стосується періоду від дня $A_j$ до дня $B_j$ включно.

Вихідні дані

Виведіть $Q$ рядків у стандартний вивід. У рядку $j$ ($1 \le j \le Q$) виведіть ціле число — найбільшу важливість для запиту $j$.

Обмеження

Усі вхідні дані задовольняють такі умови.

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

Підзадачі

Підзадача 1 [5 балів]

Виконуються такі умови.

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

Підзадача 2 [10 балів]

Виконуються такі умови.

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

Підзадача 3 [25 балів]

• Не існує $i,j$ ($1 \le i \le Q$, $1 \le j \le Q$, $i \ne j$), для яких $A_i \le A_j \le B_j \le B_i$.

Підзадача 4 [60 балів]

Додаткових обмежень немає.

Приклади

Вхідні дані 1

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

Вихідні дані 1

9
8
8
16
16

Пояснення

• Цей щоденник охоплює $5$ днів, а тип кожної події в ньому — один із $7,8,9$.
• У період від дня $1$ до дня $2$ важливість типу $7$ дорівнює $7\times 0=0$, важливість типу $8$ дорівнює $8\times 1=8$, а важливість типу $9$ дорівнює $9\times 1=9$. Отже, найбільше значення дорівнює $9$.
• У період від дня $3$ до дня $4$ важливість типу $7$ дорівнює $7\times 1=7$, важливість типу $8$ дорівнює $8\times 1=8$, а важливість типу $9$ дорівнює $9\times 0=0$. Отже, найбільше значення дорівнює $8$.
• У день $4$ важливість типу $7$ дорівнює $7\times 0=0$, важливість типу $8$ дорівнює $8\times 1=8$, а важливість типу $9$ дорівнює $9\times 0=0$. Отже, найбільше значення дорівнює $8$.
• У період від дня $1$ до дня $4$ важливість типу $7$ дорівнює $7\times 1=7$, важливість типу $8$ дорівнює $8\times 2=16$, а важливість типу $9$ дорівнює $9\times 1=9$. Отже, найбільше значення дорівнює $16$.
• У період від дня $2$ до дня $4$ важливість типу $7$ дорівнює $7\times 1=7$, важливість типу $8$ дорівнює $8\times 2=16$, а важливість типу $9$ дорівнює $9\times 0=0$. Отже, найбільше значення дорівнює $16$.

Вхідні дані 2

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

Вихідні дані 2

27
18
19
19

Пояснення

Ці вхідні дані задовольняють обмеження підзадачі 3.

Вхідні дані 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

Вихідні дані 3

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