3-й этап Республиканской олимпиады по информатике 2021-2022, 2 тура

Есеп С. Үштік

Ограничение по времени:

1 second

Ограничение по памяти:

256 megabytes

Сізге ұзындығы $n$ болатын $a$ атаулы сандар тізбегі және $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 )