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.