3-й этап Республиканской олимпиады по информатике 2021-2022, 2 тура
Задача C. Тройка
Ограничение по времени:
1 секунда
Ограничение по памяти:
256 мегабайт
Вам дана последовательность чисел $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 <= n, q <= 10^5)$.
В следующей строке даны $n$ целых чисел $a_1, a_2, \ldots a_n$ $(1 <= a_i <= 10^9)$ — последовательность чисел.
В следующих $q$ строках даны по два целых числа $l_i, r_i$ $(1 <= l_i <= r_i <= 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Вход
6 1 999370245 75 860 26427 218288294 917 1 6Ответ
731295209( Batyr Sardarbekov )
Комментарий/решение:
Возможно, что при неправильном наборе формул, они будут
доредактированы модератором. При этом содержание не будет меняться.