Pismo

Σε ένα μικρό χωριό, έξω από το Đakovo, ζει ο Kasap. Ενώ η γεωργία είναι ο κλάδος, η αγάπη και το πεπρωμένο του, στον ελεύθερο χρόνο του ο Kasap λύνει προβλήματα σχετικά με τον διαγωνιστικό προγραμματισμό και τα πάει πολύ καλά. Ιδιαίτερα ενδιαφέρουσες είναι οι εργασίες που αφορούν δομές δεδομένων.

Μια ηλιόλουστη καλοκαιρινή μέρα, ο φίλος του Kasap, ο Mirko του έστειλε ένα γράμμα που μεταφέρουμε εξ ολοκλήρου:

"Αγαπητέ μου Kasap, Ελπίζω να αντέχεις αυτές τις ζεστές μέρες του καλοκαιριού. Γράφω αυτό το γράμμα γιατί έχω πρόβλημα.
Ένας φίλος μου έδωσε μια δύσκολη αποστολή που δεν έχω καταφέρει να λύσω ακόμα. Εφόσον ξέρω
ότι σου αρέσουν αυτού του είδους οι εργασίες, θα σου ζητήσω βοήθεια γιατί δεν θέλω να ντρέπομαι μπροστά
στον φίλο μου. Στην εργασία υπάρχει ένας πίνακας ~A~ που αποτελείται από ~N~ ακέραιους αριθμούς. Θα πρέπει να βρεις ένα διάστημα με την
ελάχιστη τιμή. Η τιμή του διαστήματος ~[L, R]~ ορίζεται ως η διαφορά μεταξύ της μέγιστης και της ελάχιστης τιμής των αριθμών σε αυτό το διάστημα: ~max(A[L], A[L+1], ...,~
~A[R]) - min(A[L], A[L+1], ..., A[R])~. Να σου υπενθυμίσω ότι παρατηρούμε μόνο τα διαστήματα στα οποία το ~L~ είναι αυστηρά μικρότερο από το ~R~. Ευχαριστώ, Mirko"

Μετά από μια εβδομάδα επίλυσης, ο Kasap δεν έχει καταφέρει ακόμα να λύσει την εργασία και σας ζητά να τον βοηθήσετε.

Είσοδος

Στην πρώτη γραμμή εισόδου υπάρχει ένας θετικός ακέραιος αριθμός ~N~ ~(2 \le N \le 100\,000)~.
Στη δεύτερη γραμμή εισόδου υπάρχουν ~N~ ακέραιοι, των οποίων η απόλυτη τιμή είναι μικρότερη από ~10^9~.

Έξοδος

Εκτυπώστε την ελάχιστη τιμή ενός διαστήματος.

Βαθμολογία

Σε παραδείγματα αξίας 20 πόντων θα ισχύει ~N \le 100~. Σε παραδείγματα αξίας 40 πόντων θα ισχύει ~N \le 2\,000~.

Παραδείγματα

input

2
1 3

output

2

input

3
1 1 1

output

0

input

5
1 2 1 2 1

output

1

Επεξήγηση του 3ου παραδείγματος:

Το μέγιστο στο διάστημα ~[1, 5]~ είναι 2, ενώ το ελάχιστο στο ίδιο διάστημα είναι 1, οπότε η τιμή αυτού του διαστήματος είναι ~2 - 1 = 1~, που είναι επίσης η ελάχιστη δυνατή τιμή ενός διαστήματος.