Submit solution

Points: 1
Time limit: 0.35s
Memory limit: 64M

Author:
Problem type

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
Standardni ulaz          Standardni izlaz
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.

Comments

There are no comments at the moment.