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

Задача E. Сложная сумма

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

2.5 секунд

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

512 мегабайт

Дан массив из $n$ чисел, а также $m$ запросов. Каждый запрос содержит два числа $l$ и $r$ ($1 <= l <= r <= n$). Необходимо для каждого запроса вычислить сумму всех подмассивов $f(a[x...y])^T$ от $l$ до $r$, где $a[x...y]$ - это часть исходного массива, начинающаяся с $x$ и заканчивающаяся $y$ ($l <= x <= y <= r$), то есть массив [$a_{x}, a_{x+1}, ..., a_y$]. Для массива $b$ длины $k$, функция $f(b)$ находит массив $c$ длины $k$, который представляет собой префикс-максимумы массива $b$, а затем считает количество уникальных чисел в массиве $c$. Более формально, пусть $c_i$ = max($b_1, b_2, ..., b_i$). Тогда $f(b)$ равна количеству уникальных чисел в массиве $c$. Например, для массива $b = [3, 1, 4, 1, 5, 9, 2, 6, 5]$, мы получаем массив префикс-максимумов $c = [3, 3, 4, 4, 5, 9, 9, 9, 9]$. Затем мы считаем количество уникальных чисел в $c$, которое равно $4$ ($3, 4, 5$ и $9$). Ваша задача - написать программу, которая будет для каждого запроса будет находить сумму всех его подмассивов. Так как ответ может быть очень большим, выведите его по модулю $10^9 + 7$.

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

В первой строке заданы три целых числа $n$, $m$ и $T$($1 <= n,m <= 5 \cdot 10^5, 1 <= T <= 2$). Во второй строке заданы $n$ целых чисел $a_1, a_2, ..., a_n$($1 <= a_i <= n$). В следующих $m$ строках заданы по два целых числа $l_i$ и $r_i$ ($1 <= l_i <= r_i <= n$).

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

Выведите $m$ целых числа — ответ на каждый запрос по модулю $10^9 + 7$.

Примеры:

Вход

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

Ответ

41
6
12
12
3
6

Вход

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

Ответ

13
14
16
8
35

Замечание

Рассмотрим $4$-й запрос первого примера: $l_4 = 1, r_4 = 3$. Получается нам нужно посчитать сумму $f(a[1...1])^2 + f(a[1...2])^2 + f(a[1...3])^2 + f(a[2...2])^2 + f(a[2...3])^2 + f(a[3...3])^2 = 1 + 2^2 + 2^2 + 1 + 1 + 1 = 12$. $f(a[1..3]) = f([a_1, a_2, a_3]) = f(1, 3, 2) = 2$, так как массив префиксных максимумов будет выглядит как $[1, 3, 3]$ и в ней два различных числа. ( Aidos Nurmash )