404040: GYM101401 D Roads (A)

There are N cities numbered from 1 to N with N roads connecting them. The i^th 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 i^th road is w_i.

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).

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

The second line of input contains N space-separated integers w_i (1 ≤ w_i ≤ 1000), the i^th value represents the length of the i^th road.

Print the required sum on a single line.

4
1 1 1 1

8

5
4 2 3 1 3

38