34048번 - 월향 조각사

문제

조각의 신 아이보리는 본인의 능력을 널리 뽐내고자 1ドル \times 1$ 대리석 블록들을 이용하여 피라미드 조각상을 만들려고 한다.

크기가 $h (h \geq 1, h$는 정수$)$인 피라미드는 다음 조건을 만족해야 한다.

• 전체 너비가 2ドルh - 1$이다.
• 피라미드를 이루는 위치는 연속해야 한다.
• 피라미드를 이루는 위치의 높이가 순서대로 1,ドル 2, \cdots, h - 1, h, h - 1, \cdots, 2, 1$이다.
• 피라미드를 이루지 않는 위치의 높이는 0ドル$이다.

현재 아이보리의 작업실에는 $i$번 위치에 대리석 블록 $A_i$개가 세로로 쌓여있다. 일류 조각가인 아이보리는 본인이 조각할 수 있는 피라미드의 수가 궁금해졌다.

$f(h)$를 대리석 블록을 적절히 제거하여 크기 $h$인 피라미드를 조각하는 경우의 수라고 정의할 때, $\sum{f(h)}$를 구해보자! 단, 피라미드의 크기와 중심의 위치가 모두 같으면 같은 경우로 취급한다.

입력

첫 번째 줄에 대리석의 개수 $N$이 주어진다. $(1 \leq N \leq 200,000円)$

두 번째 줄에 $i$번 위치에 쌓여 있는 대리석 블록의 개수 $A_1, A_2, \cdots, A_N$이 공백으로 구분되어 주어진다. $(1 \le A_i \le 10^9)$

출력

첫 번째 줄에 $\sum{f(h)}$를 출력한다.

제한

힌트