مع الصغير كوستيك، تقومان ببناء أبراج من المكعبات. لقد بنيتما بالفعل $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$. يوضح الرسم التخطيطي أدناه أحد هذه الاحتمالات المثلى:
