Dat je niz od ~N~ celih brojeva, potrebno je zameniti dva broja u tom nizu nekim brojem (bilo kojim, ne obavezno iz niza), ne obavezno istim, tako da najveća razlika između dva susedna elementa bude najmanja moguća.

Opis ulaza

U prvoj liniji standardnog ulaza nalazi se broj ~N~ koji predstavlja dužinu niza.
U drugoj liniji standardnog ulaza nalazi se ~N~ celih brojeva koji predstavljaju članove zadatog niza.

Opis izlaza

U prvoj i jedinoj liniji standardnog izlaza ispisati jedan prirodan broj, najveću razliku susednih elemenata nakon izvršenih zamena tako da ta razilka bude što manja.

Primer 1

Ulaz

5
5 7 2 3 4

Izlaz

1

Primer 2

Ulaz

6
2 7 12 7 9 3

Izlaz

5

Objašnjenje test primera:

U prvom test primeru minimalna najveća razlika je 1 i može se postići na više različitih načina, jedan od njih je ako broj 7 zamenimo brojem 5, a broj 2 zamenimo brojem 4. Niz će tada izgledati: 5 5 4 3 4

Ograničenja i podzadaci

~2 \le N \le 10^5~
~-10^9 \le A_i \le 10^9~ (~0 \le i \le N-1~)

Test primeri su podeljeni u 2 disjunktne grupe:

• U test primerima vrednim 20 poena: ~N \le 200~.
  
• U test primerima vrednim 80 poena: Nema dodatnih ograničenja.
  

Napomena

Razlika između brojeva 1 i 5 je 4, bez obzira koji od njih se prvi pojavi u nizu (brojevi 5 i 1 se takođe razlikuju za 4).
U opštem slučaju, razlika između susednih brojeva u nizu ~a~ i ~b~ je ~|a-b|~