Problem description

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 10¹⁸.

Ograniczenia

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

Częściowa punktacja

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

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

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

Przykład

3
3 5 1

32