The MAPS executives, the president, vice president, and treasurer, are coordinating an Olympic artistic gymnastics showcase after a workshop. To plan the balance beam routine, they place marks ~0, 1, \ldots, n~ along the beam. Mark ~0~ is the start, and mark ~n~ is the finish.

For every destination mark ~i~ with ~1 \leq i \leq n~, the judges assign a landing coefficient ~c_i~.

A gymnast may move from any mark ~j~ to any destination mark ~i~. The mark ~j~ may be before or after ~i~, since a routine is allowed to change direction. Landing at ~i~ costs:

$$\displaystyle |j-i| \times c_i $$

Find the minimum total cost needed to reach mark ~n~.

Input

The first line contains one integer ~n~ (~1 \leq n \leq 10^6~): the number of destination marks.

The second line contains ~n~ integers ~c_1, c_2, \ldots, c_n~ (~1 \leq c_i \leq 10^9~), where ~c_i~ is the landing coefficient of mark ~i~.

Output

Print one integer: the minimum total cost.

Example 1

Input

3
5 4 5

Output

13

Example 2

Input

1
5

Output

5

Example 3

Input

4
1 1 1 1

Output

4

Example 4

Input

5
3 2 3 2 4

Output

12