Anneal

Glass is produced molten in melting furnaces, where very high temperatures prevail, and gradually cooled uniformly and in a controlled manner, in order to avoid breakage or cracks, and to maintain high product quality. A glass production company has a series of ~N~ cooling chambers and cools the product by passing it successively through all of them. The chambers are located in a straight line and are numbered along it, starting from the one closest to the melting furnace. Before the production process begins, the temperature ~a_i~ prevailing in each cooling chamber ~i~ is known. In order for the cooling process to proceed without problems, care is taken so that as the glass passes from one chamber to the next, there is no increase in temperature. This is achieved either by reducing the temperature of a chamber ~i~ from ~a_i~ to ~b_i~, which requires energy equal to the temperature difference ~a_i - b_i~, or by bypassing chamber ~i~, which requires energy equal to twice the temperature ~a_i~. The existing infrastructure of the company does not allow either an increase in the temperature of a chamber or any rearrangement of the chambers in the sequence through which the glass passes through them (meaning the glass cannot pass through another chamber ~j~ before passing through chamber ~i~).

The minimum required amount of energy to have a sequence of chambers along which the temperature does not increase is requested.

Input Files

The first line of input will contain exactly one integer: the number of chambers ~N~. The second line will contain ~N~ positive integers ~a_1~, ~... a_N~ separated by spaces: the initial temperatures of the chambers.

Output Files

The output should consist of one line containing exactly one integer: the minimum required amount of energy to have a sequence of chambers along which the temperature does not increase.

Constraints

~2 \le N \le 50.000~
~1 \le a_i \le 10.000.000~
Execution time limit: 1 sec.

Example of Input - Output Files:

STDIN (anneal.in)

8
55 10 80 50 20 40 70 60

STDOUT (anneal.out)

135

Explanation of the Example

We bypass the ~2~nd and the ~5~th chambers, and we reduce the temperature of the ~3~rd chamber to ~55~, and of the ~7~th and ~8~th chambers to ~40~. The resulting sequence of temperatures is [~55~, ~x~, ~55~, ~50~, ~x~, ~40~, ~40~, ~40~], where "~x~" denotes the chambers that have been bypassed. The energy cost is: ~(80 - 55) + (70 - 40) + (60 - 40) = 75~ for reducing the temperature in chambers ~3~, ~7~, and ~8~ respectively, and ~2 \times 10 + 2 \times 20 = 60~ for chambers ~2~ and ~5~, respectively, that we bypassed.