Qəzəbli İnəklər (Qızıl)#10598
Bessi inək öz fikrincə növbəti məşhur video oyun olacaq bir şey hazırlamışdır: "Qəzəbli İnəklər". Bessinin tamamilə orijinal hesab etdiyi oyunun süjeti aşağıdakı kimidir: oyunçu inəyi sapandla bir ölçülü səhnəyə - ədəd oxu üzərində müxtəlif nöqtələrdə yerləşən çoxlu saman topaları olan bir sahəyə - atır. İnək yerə o qədər güclə düşür ki, düşdüyü yerin yaxınlığındakı saman topalarını partladır, bu isə öz növbəsində əlavə saman topalarının partlamasına səbəb olan zəncirvari reaksiyanı işə sala bilər. Oyunun məqsədi — tək bir inəkdən istifadə edərək bütün saman topalarını məhv edəcək zəncirvari reaksiyanı başlatmaqdır.
Ədəd oxu üzərində saman topası müxtəlif tam ədəd nöqtələrində x_1, x_2, \ldots, x_n yerləşir. Əgər inək gücü ilə atılırsa və o nöqtəsinə düşürsə, onda radiuslu partlayış baş verir və [x - r, x + r] intervalında yerləşən bütün saman topalarını əhatə edir. Sonra bu saman topalarının özləri (hamısı eyni anda) partlayır, hər biri r - 1 partlayış radiusu ilə. Bu partlayışların əhatə etdiyi hələ partlamamış saman topaları isə (hamısı eyni anda) r - 2 partlayış radiusu ilə partlayır və bu proses davam edir.
Bütün saman topalarını nəticədə partlatmaq üçün tək bir inəyi uyğun yerə atmaqla istifadə edilə biləcək minimal gücünü tapın.
Birinci sətirdə n~(2 \le n \le 50000) tam ədədi verilir. Növbəti sətirin hər birində ədəd oxu üzərində saman topalarından birinin yerini göstərən x_i~(0 \le x_i \le 10^9) tam ədədi verilir.
Bütün saman topalarını partlatmaq üçün inəyin atılması lazım olan minimal gücünü çap edin. Cavab dəqiq bir onluq rəqəmə qədər yuvarlaqlaşdırılıb çap edilməlidir.
Bu misalda, məsələn, nöqtəsinə gücü ilə atılan inək dərhal və nöqtələrindəki saman topalarını partladır. Sonra bu topalar eyni anda, hər biri partlayış radiusu ilə partlayaraq və nöqtələrindəki topaları əhatə edir. Sonra bu topalar eyni anda radiusu ilə partlayaraq nöqtəsindəki son topanı əhatə edir, o da öz növbəsində radiusu ilə partlayır.
Nümunə 1