Профессор Джой, ведущий исследователь истории страны IOI, получил дневник, который, как считается, был написан жителем древней страны IOI. Чтобы изучить по этому дневнику жизнь в древней стране IOI, профессор решил исследовать описанные в нём события.

Дневник охватывает $N$ дней и содержит ровно одно событие за каждый день. События разделены на несколько типов. Тип события в день $i$ ($1\le i\le N$) задаётся целым числом $X_i$. Считается, что чем больше значение $X_i$, тем масштабнее событие.

Профессор Джой решил анализировать дневник следующим образом.

1. Выбрать в качестве периода анализа несколько последовательных дней из $N$ дней дневника.
2. Определить важность типа событий $t$ как произведение $t$ на количество событий типа $t$ за выбранный период.
3. Вычислить важность каждого типа событий и найти максимальное значение.

Профессор Джой поручил вам написать программу для анализа. Она должна уметь находить максимальную важность для заданного периода.

Задание

Даны типы событий за $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\le100\,000$.
• $1\le Q\le100\,000$.
• $1\le X_i\le1\,000\,000\,000$ ($1\le i\le N$).

Подзадачи

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

Выполняются следующие условия.

• $N\le100$.
• $Q\le100$.

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

Выполняются следующие условия.

• $N\le5\,000$.
• $Q\le5\,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\times0=0$, типа $8$ — $8\times1=8$, типа $9$ — $9\times1=9$. Поэтому максимальное значение равно $9$.
• За дни с 3 по 4 важность типа $7$ равна $7\times1=7$, типа $8$ — $8\times1=8$, типа $9$ — $9\times0=0$. Поэтому максимальное значение равно $8$.
• За день 4 важность типа $7$ равна $7\times0=0$, типа $8$ — $8\times1=8$, типа $9$ — $9\times0=0$. Поэтому максимальное значение равно $8$.
• За дни с 1 по 4 важность типа $7$ равна $7\times1=7$, типа $8$ — $8\times2=16$, типа $9$ — $9\times1=9$. Поэтому максимальное значение равно $16$.
• За дни с 2 по 4 важность типа $7$ равна $7\times1=7$, типа $8$ — $8\times2=16$, типа $9$ — $9\times0=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