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

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

Вам дана последовательность чисел $a$ длины $n$ и $q$ запросов.

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

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

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

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

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

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

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

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

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

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

Примеры

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

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

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

300
36
120
6
0