Rezolvare PBinfo #3876

Cerința

Se dă un șir de N numere întregi. Pentru fiecare subșir nevid al șirului dat se consideră valoarea întreagă D egală cu diferența dintre elementul maxim și cel minim aflat în subșir. Să se afle suma valorilor D ale tuturor subșirurilor nevide, mai mici sau egale decât un număr întreg T dat modulo \( {10}^{9} + 7 \).

Date de intrare

Programul citește de la tastatură numerele N și T, iar apoi N numere întregi, separate prin spații.

Date de ieșire

Programul va afișa pe ecran valoarea cerută în enunț.

Restricții și precizări

• 1 ≤ N, T ≤ 1.000.000
• cele N numere citite vor fi din intervalul [0, 1.000.000]
• se numește subșir al unui șir o succesiune de elemente(nu neapărat consecutive în acesta) ale acestuia, considerate în ordinea în care apar în șir
• pentru teste în valoare de 20 de puncte N ≤ 20

Exemplu:

Intrare

5 2
1 7 2 3 4

Ieșire

11

Explicație

Dacă considerăm șirul indexat de la 1, un exemplu de subșir ce respectă condiția din enunț este cel format din elementele de pe pozițiile 1, 3 și 4, D fiind egal în acest caz cu 2, deci egal cu T = 2. Un alt subșir bun este cel format de elementele de pe pozițiile 3, respectiv 4, D fiind egal în acest caz cu 1, deci mai mic decât T = 2. Subșirul format de elementele de pe pozițiile 2 și 3 nu respectă condiția din enunț pentru că în cazul acestuia D = 5 > T = 2. Analizând toate subșirurile se obține în final suma 11.