Dat je niz od $N$ kula kockica, kao na slici. Za svaku kulu je poznato od koliko je kockica sagrađena tj. koliko je visoka.

U jednom koraku se može izabrati bilo koji uzastopni niz kula i sa svake kule skinuti po 1 kockica ili na svaku kulu dodati po 1 kockica. To jest, izabrati $i$ i $j$ $(1 \le i \le j \le N)$, i uzastopni podniz kula $A_{i}, A_{i+1}, ..., A_{j}$ (gde $A_{k}$ označava visinu $k$-te kule) promeniti na $A_{i}+1, A_{i+1}+1, ..., A_{j}+1$ ili na $A_{i}-1, A_{i+1}-1, ..., A_{j}-1$.

Potrebno je odrediti najmanji broj koraka tako da sve kule postanu iste visine.

Opis ulaza

U prvoj liniji standardnog ulaza nalazi se prirodan broj $N$ $(1 \le N \le 10^6)$ koji označava broj kulica u nizu. U drugoj liniji nalazi se $N$ prirodnih brojeva razdvojenih razmakom $A_{1}, A_{2}, ..., A_{N}$ $(1 \le A_{i} \le 10^9)$, gde $A_{i}$ označava početnu visinu $i$-te kule.

Opis izlaza

U prvoj i jednoj liniji standardnog izlaza ispisati najmanji broj potrebnih koraka da se sve kulice svedu da istu visinu.

Primeri

4
6 7 4 5

3

1
1000000000

0

Objašnjenje prvog test primera:

Jedan moguć najkraći niz koraka koji dovodi do kulica istih visina je:

1. Sa kule broj 2 se izbaci 1 kockica.
2. Sa kula broj 1 i 2 se izbaci po 1 kockica.
3. Na kulu broj 3 se doda 1 kockica.

Slika niza kula na početku i nakon svakog od 3 koraka:

Ograničenja

$1 \le N \le 10^6$, $1 \le A_{i} \le 10^9$

Test primeri su podeljeni u 4 disjunktne grupe:

• U test primerima vrednim 20 poena: $1 \le N \le 100$, $1 \le A_{i} \le 100$
  
• U test primerima vrednim 20 poena: $1 \le N \le 10^5$, $1 \le A_{i} \le 100$
  
• U test primerima vrednim 40 poena: $1 \le N \le 10^5$
  
• U test primerima vrednim 20 poena: Nema dodatnih ograničenja.