수열 압축 1s 64MB

문제

수열 a₁, a₂, ..., a_n이 주어질 때, 연산 compress(i) 를 다음과 같이 정의한다.

원소 a_i와 a_i+1 을 지우고 max(a_i, a_i+1) 을 삽입한다.

이때, 발생하는 비용은 max(a_i, a_i+1) 이다.

위와 같은 연산을 n-1번 하면 하나의 수만 남는다.

수열 a₁, a₂, ..., a_n이 주어질 때, 최소의 비용으로 길이 1의 수열이 되도록

연산 compress(i) 의 수행 순서를 찾는 프로그램을 작성하시오.

입력의 첫째 줄에는 수열의 길이를 나타내는 정수 N ( 1 ≤ N ≤ 1,000,000)이 주어진다.

다음 N개의 줄 각각에는 수열의 한 원소 a_i가 주어진다 (0 ≤ a_i ≤ 1,000,000,000).

출력은 정확히 한 줄에 주어진다.

연산 compress(i)를 수행해서 길이 1인 수열을 만드는 최소비용을 출력한다.

3
keyboard_return
1
keyboard_return
2
keyboard_return
3

comkiwer

로그인해야 코드를 작성할 수 있어요.