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

Есеп E. Қиын қосынды

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

2.5 seconds

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

512 megabytes

$n$ элементтен тұратын жиым мен $m$ сұраныстар берілген. Әр сұраныс екі, $l$ және $r$ ($1 <= l <= r <= n$) сандарымен сипатталған. Әрбір сұраныс үшін $l$-ден $r$-ге дейін, барлық ішжиымдардың $f(a[x...y])^T$ қосындын санау керек. Мұндағы $a[x...y]$ бұл бастапқы жиымның $x$-тан $y$-ға дейінгі бөлімі, яғни [$a_{x}, a_{x+1}, ..., a_y$], ($l <= x <= y <= r$) жиымы. Ұзындығы $k$ болатын $b$ жиымы үшін $f(b)$ функциясы, ол $b$ жиымының префикс-максимумымдарын құрайтын, ұзындығы $k$ болатын $c$ жиымын тауып, содан кейін $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 )