Berries for the Lemurs

Interview

Time limit2sMemory limit1024 MB

Summary

Given n lemurs with love levels a_i, find the sum over each i of a_i times the number of earlier lemurs j whose reach j+a_j extends past i.

Level: Medium4 of 10
Topics: Prefix sum, Array
Solved: No attempts yet

Statement

Lemurs are cute animals that live on the island of Madagascar. Their leader is an energetic and charming lemur who calls himself King Julian. One of his royal duties is handing out berries to all of his subjects.

To hand out the berries, King Julian lines up all lemurs of his tribe in a row. Besides its number $i$ in this row, each lemur has a non-negative integer $a_i$ , its level of love for King Julian. The number of berries each lemur receives depends on how much he and his neighbors in the row love their leader.

Before giving berries to lemur number $i$ , Julian counts the lemurs with numbers $j < i$ such that $j + a_j > i$ . He then multiplies this count by $a_i$ , and the result is the number of berries lemur $i$ receives.

Find the total number of berries Julian has to hand out.

Input

The first line contains one integer $n$ , the number of subjects of King Julian. The next line contains $n$ integers $a_i$ ( $0 \le a_i \le n$ ), the lemurs' levels of love for their leader.

Output

Print one integer, the total number of berries King Julian has to hand out.

Hint

The answer for the sample is computed by the formula $0 \times 4 + 1 \times 2 + 2 \times 2 + 2 \times 4 = 14$ .

Examples1

Example 1
Input
```
4
4 2 2 4
```
Expected output
```
14
```