Problem 3806: Circuit

Iaroslav-Menelaos Popescu, zis și Trăznetul Zalăului de Sud, sau (din partea prietenilor) Iaro-Laos, inexplicabil are chef să se uite la maximele subșirurilor subsecvențelor unui șir. De când e mic copil, Iaro-Laos mereu a avut interese neobișnuite.

Mai exact, Iaro-Laos definește
valoarea circuitului complet unui șir $a_1, \ldots, a_n$ , notată $\text{circ}(a_1, \ldots, a_n)$ , ca fiind suma maximelor tuturor subșirurilor lui $a_1, \ldots, a_n$ . Mai exact

\text{circ}(a_1, \ldots, a_n) = \sum_{k = 1}^n \sum_{1 \leq i_1 < \cdots < i_k \leq n}\max(a_{i_1}, \ldots, a_{i_k}).

Cerință

Se dă un șir de numere $a_1, \ldots, a_n$ . Să se calculeze

\sum_{i = 1}^n \sum_{j = i}^n \text{circ}(a_i, \ldots, a_j) \pmod{10^9 + 7}

Date de intrare

Primul rând conține numărul $n$ . Pe al doilea rând conține numerele $a_1, \ldots, a_n$ .

Date de ieșire

Afișați răspunsul cerut.

Restricții

$1 \leq n \leq 300\ 000$ .
$0 \leq a_i \leq 1\ 000\ 000\ 000$ .

#	Scor	Restricții
1	4	$n \leq 15$ .
2	5	Șirul este strict crescător.
3	11	$n \leq 300$ .
4	14	$n \leq 3 \ 000$ .
5	28	$n \leq 80 \ 000$ .
6	38	Fără restricții suplimentare.

Exemplu

stdin

5
5 3 2 4 1

stdout

Explicații

Observăm că

\begin{aligned} \operatorname{val}(1) &= \max(1) = 1 \\ \operatorname{val}(4,1) &= \max(4) + \max(1) + \max(4,1) = 4 + 1 + 4 = 9 \\ \operatorname{val}(2,4,1) &= \max(2) + \max(4) + \max(2,4) + \max(1) + \max(2,1) + \max(4,1) + \max(2,4,1) \\ &= 2 + 4 + 4 + 1 + 2 + 4 + 4 = 21 \\ \operatorname{val}(3,2,4,1) &= \max(3) + \max(2) + \max(3,2) + \max(4) + \max(3,4) + \max(2,4) + \max(3,2,4) \\ &\quad + \max(1) + \max(3,1) + \max(2,1) + \max(3,2,1) + \max(4,1) + \max(3,4,1) \\ &\quad + \max(2,4,1) + \max(3,2,4,1) \\ &= 3 + 2 + 3 + 4 + 4 + 4 + 4 + 1 + 3 + 2 + 3 + 4 + 4 + 4 + 4 = 49 \\ \operatorname{val}(5,3,2,4,1) &= \max(5) + \max(3) + \max(5,3) + \max(2) + \max(5,2) + \max(3,2) + \max(5,3,2) \\ &\quad + \max(4) + \max(5,4) + \max(3,4) + \max(5,3,4) + \max(2,4) + \max(5,2,4) + \max(3,2,4) \\ &\quad + \max(5,3,2,4) + \max(1) + \max(5,1) + \max(3,1) + \max(5,3,1) + \max(2,1) + \max(5,2,1) \\ &\quad + \max(3,2,1) + \max(5,3,2,1) + \max(4,1) + \max(5,4,1) + \max(3,4,1) + \max(5,3,4,1) \\ &\quad + \max(2,4,1) + \max(5,2,4,1) + \max(3,2,4,1) + \max(5,3,2,4,1) \\ &= 5 + 3 + 5 + 2 + 5 + 3 + 5 + 4 + 5 + 4 + 5 + 4 + 5 + 4 + 5 + 1 + 5 + 3 + 5 \\ &\quad + 2 + 5 + 3 + 5 + 4 + 5 + 4 + 5 + 4 + 5 + 4 + 5 = 129 \\ \operatorname{val}(4) &= \max(4) = 4 \\ \operatorname{val}(2,4) &= \max(2) + \max(4) + \max(2,4) = 2 + 4 + 4 = 10 \\ \operatorname{val}(3,2,4) &= \max(3) + \max(2) + \max(3,2) + \max(4) + \max(3,4) + \max(2,4) + \max(3,2,4) \\ &= 3 + 2 + 3 + 4 + 4 + 4 + 4 = 24 \\ \operatorname{val}(5,3,2,4) &= \max(5) + \max(3) + \max(5,3) + \max(2) + \max(5,2) + \max(3,2) + \max(5,3,2) \\ &\quad + \max(4) + \max(5,4) + \max(3,4) + \max(5,3,4) + \max(2,4) + \max(5,2,4) \\ &\quad + \max(3,2,4) + \max(5,3,2,4) \\ &= 5 + 3 + 5 + 2 + 5 + 3 + 5 + 4 + 5 + 4 + 5 + 4 + 5 + 4 + 5 = 64 \\ \operatorname{val}(2) &= \max(2) = 2 \\ \operatorname{val}(3,2) &= \max(3) + \max(2) + \max(3,2) = 3 + 2 + 3 = 8 \\ \operatorname{val}(5,3,2) &= \max(5) + \max(3) + \max(5,3) + \max(2) + \max(5,2) + \max(3,2) + \max(5,3,2) \\ &= 5 + 3 + 5 + 2 + 5 + 3 + 5 = 28 \\ \operatorname{val}(3) &= \max(3) = 3 \\ \operatorname{val}(5,3) &= \max(5) + \max(3) + \max(5,3) = 5 + 3 + 5 = 13 \\ \operatorname{val}(5) &= \max(5) = 5 \end{aligned}

Așadar calculăm

1 + 9 + 21 + 49 + 129 + 4 + 10 + 24 + 64 + 2 + 8 + 28 + 3 + 13 + 5 = 370.

Circuit