베시는 농부 존에게 우유 양동이를 이용한 게임을 도전했다!
일렬로 놓인 우유 양동이가 N개(2≤N≤2⋅10^5) 있으며, 왼쪽에서 i번째 양동이에는 처음에 a_i (0≤a_i≤10^9) 갤런의 우유가 들어 있다.

이 게임은 두 단계로 이루어져 있다.

1단계:
농부 존은 서로 인접한 두 양동이를 아무 쌍이나 서로 바꿀 수 있다.
원하는 만큼 교환할 수 있지만, 각 교환에는 동전 1개가 든다.

2단계:
교환이 끝난 후, 농부 존은 양동이가 하나만 남을 때까지 다음 연산을 수행한다:
우유의 양이 a_i와 a_{i+1}인 서로 인접한 두 양동이를 선택하여, 그 자리에 우유가 \frac{a_i+a_{i+1}}{2} 갤런 들어 있는 하나의 양동이로 두 양동이를 대체한다.

당신의 목표는 모든 병합이 완료된 후 최종 양동이에 들어 있는 우유의 양을 최대화하기 위해, 농부 존이 교환 단계에서 지불해야 하는 동전의 최소 개수를 구하는 것이다.

#8859 upload - done - how_to_reg - call_split Subtarea

우유 양동이 timer 1s memory 1024MB

#8859
Subtarea

우유 양동이 1s 1024MB