단열재

Insumax 사는 여러 겹으로 이루어진 단열재를 만든다. 단열재는 $n$개의 층으로 구성되며, $i$번째 층($i = 1, 2, \dots, n$)은 양의 정수인 단열 계수 $a_i$로 나타낸다. 층의 번호는 열이 빠져나가는 방향을 따라 매긴다.

heat  ->  || a1 | a2 | ... | ai | ai+1 | ... | an ||  ->

단열재 전체의 단열 계수 $A$는 각 층의 단열 계수의 합으로 정해진다. 여기에 더해, 어떤 층 뒤에 그보다 단열 계수가 큰 층이 오면 두 값의 차이만큼 $A$가 커진다. 정확히는 다음과 같이 정의한다.

$A = \sum_{i=1}^{n} a_i + \sum_{i=1}^{n-1} \max(0,\ a_{i+1} - a_i)$

예를 들어 층을 $5, 4, 1, 7$ 순서로 놓으면 $A = (5 + 4 + 1 + 7) + (7 - 1) = 23$이다.

주어진 층들의 단열 계수 $a_1, a_2, \dots, a_n$을 적절히 배열하여 단열재 전체의 단열 계수 $A$를 최대로 만들었을 때, 그 최댓값을 출력하는 프로그램을 작성하시오.

첫째 줄에 층의 개수 $n$이 주어진다($1 \le n \le 100000$). 이어지는 $n$개의 줄에 각 층의 단열 계수 $a_1, a_2, \dots, a_n$이 한 줄에 하나씩 주어진다. 각 계수는 $1 \le a_i \le 10000$을 만족하는 정수이다.

층을 적절히 배열했을 때 얻을 수 있는 단열재 전체의 단열 계수 $A$의 최댓값을 한 줄에 하나의 정수로 출력한다.