Description

Original Source: HNOI 2002

Tiger was recently promoted to the position of sales manager at his company. The first task assigned to him after his promotion was to analyze the company's sales performance since its establishment.

Tiger pulled out the company's ledger, which records the daily sales since the company was founded. Analyzing sales performance is a complex task. Due to holidays, promotions, or other circumstances, sales figures can fluctuate. While some fluctuations are normal, extreme spikes or drops in sales indicate potential operational issues.

In economics, a metric called the minimum fluctuation value is used to measure this situation: let $a_i$ be the sales on a previous day, and $b$ be the sales on the current day. The minimum fluctuation value for the current day is defined as $\delta=\min |a_i-b|$. The larger the minimum fluctuation value, the more unstable the sales performance. To assess the overall stability of the company's sales performance from its establishment to the present, we simply sum up the minimum fluctuation values for each day.

Your task is to write a program to help Tiger compute this value. The minimum fluctuation value for the first day is defined as the sales on that day.

Simplified Problem Statement

Given a sequence $\{a_n\}$ of $n$ numbers, for each element $a_i$ (where $i > 1$), define $f_i=\min |a_i-a_j|$ for $1\le j\lt i$, and $f_1=a_1$. Compute the sum $\sum f_i$.

Input Format

The first line contains a positive integer, representing the number of days since the company's establishment;

The next $n$ lines each contain an integer, representing the company's sales on the $i$-th day, $a_i$.

Output Format

Output a single positive integer, the sum of the minimum fluctuation values for each day. The result is guaranteed not to exceed $2^{31}$.

Sample 1

$5+|1-5|+|2-1|+|5-5|+|4-5|+|6-5|=5+4+1+0+1+1=12$

6
5
1
2
5
4
6

12

Data Range and Hints

For all data, $1\le n\lt 2^{15}$ and $|a_i|\le 10^6$.