Problem 4212: Baronus

La o companie de făurit cărți de joc lucrează $N$ angajați. Pentru simplitate, îi vom numerota (angajații $1, 2, 3, \dots, N$ )

Baronul Job al III-lea, fiind proprietarul companiei, dorește ca compania să aibă o structură bine-definită. Deoarece această companie are o grămadă de pachete de toate felurile, acesta va folosi unul dintre ele pentru a stabili structura companiei.

Pachetul are exact $N$ cărți, numerotate de la $1$ la $N$ . Fiecare angajat va primi câte o carte diferită dintre cele $N$ . Deoarece Baronul este foarte parțial (adică nu e imparțial), el va alege ce carte va primi fiecare angajat (angajatul $i$ va primi cartea cu numărul $p_i$ ).

Baronul preferă mereu angajații cu cărți care au numere mai mari. Pentru el, autoritatea este direct proporțională cu numărul de pe carte. Astfel, dacă privim întreaga companie, persoana care deține cartea cu număr maxim va deveni Directorul Suprem al companiei.

Dar Baronul nu se oprește aici. El nu stabilește structura doar global, ci și local, pe departamente. Un departament reprezintă un grup de angajați consecutivi, de la $l$ la $r$ . În acel departament, regulile sunt simple:

Șeful acelui departament este persoana cu numărul maxim al cărții. Această persoană este șefa tuturor angajaților din acel departament.
Angajații aflați în stânga acestei persoane (de la $l$ la poziția ei minus 1) reprezintă un sub-departament (dacă aceștia există).
Angajații aflați în dreapta acestei persoane (de la poziția ei plus 1 la $r$ ) reprezintă un sub-departament (dacă aceștia există).
Fiecare sub-departament aplică aceleași reguli.

Observăm că un angajat poate avea mai mulți șefi.

Baronul are $Q$ sponsori pentru companie, iar fiecare sponsor are o întrebare pentru el. Din departamentul cu angajații de la $L$ la $R$ , ne interesează fiecare sub-departament al său.

Pentru fiecare sub-departament de la $l$ la $r$ , acesta trebuie să construiască structura ierarhică la fel ca mai sus, și să calculeze influența $s(i)$ a fiecărui angajat, adică numărul de angajați care îl au pe acesta ca șef. Sponsorii sunt interesați de suma influențelor angajaților din acest sub-departament. Mai formal, Baronul trebuie să calculeze valoarea

f(l, r) = \sum_{i=l}^r s(i)

Însă sponsorii sunt mai curioși de atât. Aceștia vor să afle suma acestor valori. Mai formal, Baronul trebuie să calculeze valoarea

F(L, R) = \sum_{l=L}^R \sum_{r=l}^R f(l,r)

Deoarece aceste valori pot fi foarte mari, sponsorii sunt doar interesați de restul lor modulo $10^9+7$ .

Însă, Baronul este foarte ocupat cu căutatul monedelor căzute pe podea, așa că cere ajutorul vostru.

Date de intrare

Prima linie va conține două numere naturale $N$ și $Q$ . A doua linie conține șirul $p_1, p_2, \dots, p_N$ . Următoarele $Q$ linii conțin câte două numere naturale $L$ și $R$ .

Date de ieșire

Pentru fiecare întrebare se afișează pe o linie valoarea corespunzătoare a $F(L,R)$ , modulo $10^9+7$ .

Restricții și precizări

$1 \leq N, Q \leq 500 \ 000$
$1 \leq L \leq R \leq N$ pentru toate întrebările.
Se garantează că șirul $p_1, p_2, \dots, p_n$ este o permutare a mulțimii $\{1, 2, \dots, n\}$ .
Un angajat nu este propriul lui șef.
Notăm cu $D$ numărul de indici $i$ astfel încât $1 \leq i < N$ și $p_i > p_{i+1}$
Notăm cu $M$ numărul de indici $i$ astfel încât $p_i > p_j$ pentru orice $j$ , $1 \leq j < i$

Subtask	Restricții	Punctaj
0	Exemplul	$0$
1	$N,Q \leq 40$	$2$
2	$N,Q \leq 100$	$3$
3	$N,Q \leq 500$	$5$
4	$N,Q \leq 2 \ 000$	$12$
5	$p_1 < p_2 < \dots < p_N$	$7$
6	$N,Q \leq 100 \ 000, D \leq 1 \ 000$	$12$
7	$N,Q \leq 100 \ 000, M \leq 1 \ 000$	$12$
8	$N,Q \leq 100 \ 000, L = 1$ pentru toate întrebările	$8$
9	$N,Q \leq 100 \ 000$	$22$
10	Fără alte restricții	$17$

Exemplu

stdin

stdout

1
5

Explicație

Pentru primul sponsor, avem

F(1, 2) = f(1, 1) + f(2, 2) + f(1, 2) = 0 + 0 + 1 = 1

Pentru al doilea sponsor, avem

F(1, 3) = f(1, 1) + f(2, 2) + f(3, 3) + f(1, 2) + f(2, 3) + f(1, 3) = 0 + 0 + 0 + 1 + 1 + 3 = 5

Baronus

Date de intrare

Date de ieșire

Restricții și precizări

Exemplu

Explicație

Log in or sign up to be able to send submissions!