장기자랑

즐거운 설날을 맞아 부대에서 장기자랑 행사가 열린다! 이 행사는 한 번에 한 명씩 순서대로 공연하는 형식으로 진행된다.

장기자랑 행사의 총관리자는 공연하는 병사들의 실력을 보고 행사를 준비하던 중, 앞에 공연한 사람이 너무 잘하면 뒤에 공연하는 사람이 부담을 느껴 제 실력을 발휘하지 못할 것이라고 걱정하게 되었다. 이에 총관리자는 다음과 같은 가설을 세웠다. 각 병사의 장기자랑 실력을 순서대로 $a\_1, a\_2, \cdots, a\_n$이라고 할 때, $2\leq i\leq N$인 모든 $i$에 대하여 $i$번째 공연자는 실력을 $\max\left(0,a\_i-a\_{i-1}\right)$만큼만 발휘할 수 있다. 이때 가장 먼저 공연하는 병사는 본인의 실력을 그대로 발휘할 수 있다.

이 가설에 따라 총관리자는 병사들이 발휘할 수 있는 실력의 합이 최대가 되도록 공연 순서를 정하려 한다. 적절한 순서로 병사들을 배치했을 때, 각 병사가 발휘할 수 있는 실력의 합의 최댓값을 구하여라.

첫 번째 줄에 병사의 수 $N$이 주어진다. $(1\leq N\leq 100\,000)$

두 번째 줄에 $N$명의 병사들의 장기자랑 실력을 나타내는 정수 $a\_i$가 공백으로 구분되어 주어진다. $(1\leq a\_i\leq 10\,000)$

적절한 순서로 $N$명의 병사들을 배치했을 때, 각 병사가 발휘할 수 있는 실력의 합의 최댓값을 출력한다.