2017 PSUT Coding Marathon |
---|
Закончено |
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).
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.
Print the required sum on a single line.
4
1 1 1 1
8
5
4 2 3 1 3
38
Название |
---|