Областная олимпиада по информатике 2022 года за 10 класс | Казахстанские олимпиады

Задача F. Тройка

Ограничение по времени Ограничение по памяти
1 секунда 256 мегабайт

Вам дана последовательность чисел aa длины nn и qq запросов.

Каждый запрос состоит из двух чисел ll и rr.

Для каждого запроса найдите следующие значение:

sumi=lrj=lrk=lrmax(ai,aj,ak)min(ai,aj,ak)sum_{i=l}^{r} \sum_{j=l}^{r} \sum_{k=l}^{r} max(a_i, a_j, a_k) - min(a_i, a_j, a_k)

Так как ответ может быть большим, выведите его по модулю 109+710^9 + 7.

Формат входного файла

В первой строке даны два целых числа nn и qq (1n,q105)(1 \leq n,q \leq 10^5).

В следующей строке даны nn целых чисел a1,a2,ana_1,a_2,…a_n (1ai109)(1 \leq a_i \leq 10^9) — последовательность чисел.

В следующих qq строках даны по два целых числа li,ril_i,r_i (1lirin)(1 \leq l_i \leq r_i \leq n) — описание ii-го запроса.

Формат выходного файла

Выведите qq целых число — ответ на задачу.

Примеры

Входные данные

5 5
1 2 3 4 5
1 5
1 3
2 5
2 3
4 4

Выходные данные

300
36
120
6
0