문제
정수로 이뤄진 수열 A1, A2, ..., An 가 주어졌을 때, 이 수열에 reduce(i) 라는 함수를 적용시키게 되면 수열에 포함된 원소의 개수가 X개에서 X-1개로 줄게 된다.
reduce(i) 함수는 A1, A2, ..., An 이었던 수열을 A1, A2, ... max(Ai, Ai+1), ..., An 으로 바꾸는 함수이다. 이때 reduce(i) 함수를 통해 소모되는 비용은 max(Ai, Ai+1) 이다. 여기서 max(X, Y)란 X와 Y중에 큰 값을 반환하는 함수다.
reduce(i) 함수를 n-1 번 적용시키게 될 경우 최종적으로 길이가 1인 수열을 얻게 되는데, reduce(i) 함수를 사용하면서 드는 비용의 합이 최소화가 되도록 하는 프로그램을 작성하라.
입력
입력의 첫줄에는 수열에 포함된 정수의 개수를 뜻하는 n(1≤n≤1,000,000)이 주어진다.
그 다음 줄부터 한 줄에 하나씩 0이상 1,000,000,000 이하의 정수로 이뤄진 A1, A2, ..., An 이 주어진다.
출력
입력에 대해 reduce 함수를 사용하여 수열의 길이를 1로 줄이기 위해 필요한 비용의 합의 최소를 출력하라.
예제
3
1
2
3
5
로그인해야 코드를 작성할 수 있어요.