노선 분할 비용

문제

한 버스 노선에는 정류장 N개가 1번부터 N번까지 일렬로 놓여 있고, i번 정류장의 혼잡도는 양의 정수 a_i 이다. 운영 본부는 노선을 다음 규칙에 따라 재귀적으로 쪼갠다. 정류장 구간 [l, r] 이 주어지면, 구간이 비어 있을 때는 아무것도 하지 않는다. 비어 있지 않으면 구간 안에서 혼잡도가 가장 큰 정류장 m 을 고른다. 혼잡도가 같은 정류장이 여럿이면 번호가 가장 작은 것을 고른다. 이 정류장을 기준으로 노선을 앞쪽 구간 [l, m−1] 과 뒤쪽 구간 [m+1, r] 로 나누며, 이때 짧은 쪽 구간의 정류장 수만큼의 임시 셔틀을 운행해야 한다. 즉 이 분할의 비용은 min(m − l, r − m) × a_m 이다. 그런 다음 앞쪽 구간과 뒤쪽 구간에 같은 규칙을 각각 다시 적용한다. 정류장이 하나뿐인 구간의 비용은 0 이다. 처음 구간은 [1, N] 이고, 모든 분할이 끝날 때까지 든 비용의 총합을 구하는 프로그램을 작성하라. 총합은 32비트 정수 범위를 넘을 수 있다. 재귀 깊이가 N 까지 깊어질 수 있으므로 구현 방식에 유의해야 한다.

입력

첫 줄에 정류장 수 N 이 주어진다. (1 ≤ N ≤ 200,000) 둘째 줄에 a_1 … a_N 이 공백으로 주어진다. (1 ≤ a_i ≤ 10^9, 정수)

출력

비용의 총합을 한 줄에 출력한다.

5
3 1 4 1 5

4

5
5 2 9 2 5

18

4
2 2 2 2

0

출처: Devin.KR 자체 제작