응답하라 262144 (262144 Revisited) timer 2초 memory 256MB

Bessie는 휴대전화로 게임을 다운로드하는 것을 좋아하지만, 큰 발굽 때문에 작은 터치스크린을 사용하는 것이 번거롭다는 것을 알게 되었습니다.

그녀는 특히 그녀가 현재 하고 있는 게임에 매료되어 있습니다. 게임은 1~10⁶ 범위에 있는 N개의 양의 정수 수열 a₁, a₂, …, a_N (2≤N≤262,144)로 시작합니다. 한 턴에 Bessie는 인접한 두 숫자를 가져와 두 숫자의 최대값보다 큰 숫자로 바꿀 수 있습니다(예: 인접한 숫자 쌍(5,7)을 8로 바꿀 수 있음). 게임은 N−1 턴후에 종료되며, 이 시점에서 남은 숫자는 하나뿐입니다. 게임의 목표는 이 최종 숫자를 최소화하는 것입니다.

베시는 이 게임이 당신에게 너무 쉽다는 것을 알고 있습니다. 따라서 귀하의 임무는 게임을 최적으로 플레이하는 것뿐만 아니라 의 연속적인 부분수열​에서 게임을 플레이하는 것입니다.

a의 모든 N*(N+1)/2 개의 부분수열에서 나올 수 있는​가능한 가장 작은 최종 값의 합계를 출력합니다.​