D. Roads (A)
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

There are N cities numbered from 1 to N with N roads connecting them. The ith road goes between the two cities i and i + 1 (1 ≤ i < N), and the last road goes between the first and the last city. The length of the ith road is wi.

Let dist(u, v) be the length of the shortest path that goes between city u and city v. Your task is to find the total sum of dist(u, v) for all pairs (u, v) (1 ≤ u < v ≤ N).

Input

The first line of input contains a single integer N (3 ≤ N ≤ 2 × 105), the number of cities.

The second line of input contains N space-separated integers wi (1 ≤ wi ≤ 1000), the ith value represents the length of the ith road.

Output

Print the required sum on a single line.

Examples
Input
4
1 1 1 1
Output
8
Input
5
4 2 3 1 3
Output
38