Problem description


Suma sum podtablic
(suma-sum-podtab)
Memory limit: 32 MB
Time limit: 3.00 s

Jasio ma tablicę nieujemnych liczb całkowitych. Potrzebuje na gwałt zsumować dziwną rzecz. Jasio rozpatruje wszystkie podtablice od dowolnego elementu do dowolnego elementu, oblicza sumę elementów wewnątrz każdej z tych podtablic i potrzebuje wiedzieć ile wynosi suma tych wszystkich sum podtablic.

Na przykład: jeśli tablica Jasia to: [3,5,1] to podtablice, które rozpatruje Jasio to: [3], [5], [1], [3,5], [5,1], [3,5,1]. Sumy tych podtablic to odpowiednio: 3, 5, 1, 8, 6, 9, a więc suma, której potrzebuje Jasio to: 3 + 5 + 1 + 8 + 6 + 9 = 32.

Pomożesz Jasiowi jak zawsze? Pokaż, że potrafisz.

Napisz program, który: wczyta tablicę Jasia, obliczy sumę sum wszystkich podtablic i wypisze wynik na standardowe wyjście.

Wejście

W pierwszym wierszu wejścia znajduje się jedna liczba naturalna N, określająca długość tablicy. W drugim (ostatnim) wierszu wejścia znajduje się ciąg N nieujemnych liczb całkowitych: kolejne elementy tablicy Jasia.

Wyjście

W pierwszym (jedynym) wierszu wyjścia należy wypisać jedną liczbę całkowitą – sumę sum podtablic Jasia.

Uwaga

Gwarantowane jest, że wynik nie przekroczy 1018.

Ograniczenia

1 ≤ N ≤ 1 000 000, 0 ≤ Ai ≤ 50 000.

Częściowa punktacja

W testach wartych łącznie 27% maksymalnej punktacji: N ≤ 100.

W testach wartych łącznie 36% maksymalnej punktacji: wszystkie Ai są równe 1.

W testach wartych łącznie 54% maksymalnej punktacji: N ≤ 5 000.

Przykład

Input Output Explanation
3
3 5 1
32

Wyjaśnienie tego przykładu znajduje się powyżej.