יחד עם קוסטק הקטן, אתם בונים מגדלים מקוביות. כבר בניתם $n$ מגדלים בשורה, כאשר הגובה של המגדל ה-$i$ הוא $h_i$. כעת קוסטק רוצה לקבוע גבול בין המגדלים שלו למגדלים שלכם. המגדלים שמשמאל לגבול יהיו שייכים לקוסטק, ושאר המגדלים שמימין יהיו שלכם. לכל אחד מכם חייב להיות לפחות מגדל אחד.
אתם עומדים לעבור למשחק הבא, שמתחיל בכך שכל אחד מכם מציב תצפיתן על המגדל הגבוה ביותר שלו. המשחק לא יהיה מהנה אם התצפיתנים יעמדו בגבהים שונים לחלוטין. לכן, עליכם להציע את החלוקה ההוגנת ביותר האפשרית – בחרו את הגבול כך שהערך המוחלט של ההפרש בין גובה המגדל הגבוה ביותר של קוסטק לבין זה שלכם יהיה מינימלי. הדפיסו הפרש מינימלי זה.
קלט
השורה הראשונה מכילה מספר שלם $n$ ($2 \le n \le 300\,000$), המציין את מספר המגדלים.
השורה השנייה מכילה $n$ מספרים שלמים $h_1, h_2, \dots, h_n$ ($1 \le h_i \le 10^9$), המציינים את הגבהים של המגדלים העוקבים משמאל לימין.
פלט
הדפיסו מספר שלם אחד – הפרש הגבהים הקטן ביותר האפשרי בין המגדל הגבוה ביותר שלכם לבין המגדל הגבוה ביותר של קוסטק.
דוגמאות
קלט 1
3 200 333 100
פלט 1
133
קלט 2
5 5 2 4 1 5
פלט 2
0
קלט 3
6 5 1 4 4 2 3
פלט 3
1
הערה
במקרה הבדיקה הראשון, קוסטק צריך לקבוע את הגבול בין שני המגדלים הראשונים. אז יש לו מגדל בגובה $200$, בעוד שלכם יש מגדלים בגבהים $333$ ו-$100$. המגדלים הגבוהים ביותר שלכם הם $200$ ו-$333$, ולכן התוצאה היא $133$. לא ניתן להשיג הפרש קטן יותר.
במקרה הבדיקה השני, כל חלוקה מניבה הפרש של $0$.
במקרה הבדיקה השלישי, קוסטק צריך לקבוע את הגבול אחרי המגדל הראשון, השני או השלישי. ההפרש המתקבל הוא $|5 - 4| = 1$. התרשים שלהלן מציג אחת מהאפשרויות האופטימליות הללו:
