262144 Revisited

Bessie는 작은 터치스크린이 큰 발굽으로 쓰기에는 불편하다고 느끼지만, 휴대폰에 게임을 내려받아 즐기는 것을 좋아한다.

그녀는 지금 하고 있는 게임에 특히 흥미를 느낀다. 게임은 각각 $1\ldots 10^6$ 범위의 양의 정수 수열 $a\_1,a\_2,\ldots,a\_N$ ($2\le N\le 262,144$)으로 시작한다. 한 번의 동작에서 Bessie는 인접한 두 수를 골라, 둘 중 큰 수보다 1 큰 수 하나로 바꾼다. 예를 들어 인접한 쌍 $(5,7)$은 $8$로 바꿀 수 있다. 게임은 $N-1$번의 동작 후 수가 하나만 남으면 끝난다. 목표는 이 최종 수를 최소화하는 것이다.

Bessie에게 이 게임은 너무 쉽다. 여러분의 과제는 $a$에 대해 게임을 최적으로 하는 것뿐 아니라, $a$의 모든 연속 부분 수열에 대해서도 같은 일을 하는 것이다.

$a$의 모든 연속 부분 수열 $\frac{N(N+1)}{2}$개에 대해, 가능한 최종 수의 최솟값을 모두 더한 합을 출력하라.

첫 줄에 $N$이 주어진다.

다음 줄에는 입력 수열을 이루는 $N$개의 정수가 공백으로 구분되어 주어진다.

합을 한 줄에 출력한다.

연속 부분 수열은 모두 $\frac{6\cdot 7}{2}=21$개이다. 예를 들어 $[1,3,1,2,1]$의 최종 수의 최솟값은 $5$이며, 다음 순서의 동작으로 얻을 수 있다.

원래 수열    -> [1,3,1,2,1]
1과 3 합치기 -> [4,1,2,1]
2와 1 합치기 -> [4,1,3]
1과 3 합치기 -> [4,4]
4와 4 합치기 -> [5]

각 연속 부분 수열의 최종 수 최솟값은 다음과 같다.

final(1:1) = 1
final(1:2) = 4
final(1:3) = 5
final(1:4) = 5
final(1:5) = 5
final(1:6) = 11
final(2:2) = 3
final(2:3) = 4
final(2:4) = 4
final(2:5) = 5
final(2:6) = 11
final(3:3) = 1
final(3:4) = 3
final(3:5) = 4
final(3:6) = 11
final(4:4) = 2
final(4:5) = 3
final(4:6) = 11
final(5:5) = 1
final(5:6) = 11
final(6:6) = 10