Bersama Kostek kecil, Anda sedang membangun menara dari balok-balok mainan. Kalian telah membangun $n$ menara dalam satu barisan, dengan menara ke-$i$ memiliki tinggi $h_i$. Sekarang Kostek ingin menetapkan batas antara menara miliknya dan menara milik Anda. Menara-menara di sebelah kiri batas akan menjadi milik Kostek, dan sisa menara di sebelah kanan akan menjadi milik Anda. Masing-masing dari kalian harus memiliki setidaknya satu menara.
Kalian akan segera beralih ke permainan berikutnya, yang dimulai dengan masing-masing dari kalian menempatkan seorang pengintai di atas menara tertinggi masing-masing. Permainan tidak akan seru jika para pengintai berdiri pada ketinggian yang sangat berbeda. Oleh karena itu, Anda harus menyarankan pembagian yang paling adil – pilih batas sedemikian rupa untuk meminimalkan nilai mutlak selisih antara tinggi menara tertinggi Kostek dan menara tertinggi Anda. Cetak selisih minimum ini.
Masukan
Baris pertama berisi sebuah bilangan bulat $n$ ($2 \le n \le 300\,000$), yang menyatakan banyaknya menara.
Baris kedua berisi $n$ bilangan bulat $h_1, h_2, \dots, h_n$ ($1 \le h_i \le 10^9$), yang menyatakan tinggi menara-menara secara berurutan dari kiri ke kanan.
Keluaran
Cetak satu bilangan bulat – selisih tinggi terkecil yang mungkin antara menara tertinggi Anda dan menara tertinggi Kostek.
Contoh
Masukan 1
3 200 333 100
Keluaran 1
133
Masukan 2
5 5 2 4 1 5
Keluaran 2
0
Masukan 3
6 5 1 4 4 2 3
Keluaran 3
1
Catatan
Pada uji pertama, Kostek sebaiknya menetapkan batas di antara dua menara pertama. Dengan demikian ia memiliki menara setinggi $200$, sedangkan Anda memiliki menara setinggi $333$ dan $100$. Menara tertinggi kalian masing-masing adalah $200$ dan $333$, sehingga hasilnya adalah $133$. Tidak mungkin mencapai selisih yang lebih kecil.
Pada uji kedua, pembagian mana pun menghasilkan selisih sebesar $0$.
Pada uji ketiga, Kostek sebaiknya menetapkan batas setelah menara pertama, kedua, atau ketiga. Selisih yang diperoleh adalah $|5 - 4| = 1$. Diagram di bawah menunjukkan salah satu dari kemungkinan optimal tersebut:
