Pis inəklər (Qızıl)
Besi yeni bir oyun icad etdi. Oyunçu, bir inəyi bir ölçülü səhnəyə atır. Bu səhnə, müxtəlif nöqtələrdə yerləşən bir çox ot tayasından ibarətdir. İnək yerə düşdükdən sonra zəncirvari partlayış reaksiyası baş verə bilər. Məqsəd, bir inəkdən istifadə edərək bütün ot tayalarını partlatmaq üçün zəncirvari reaksiya başlatmaqdır.
n ot tayası var və bunlar ədədi ox üzərində müxtəlif tam ədədi mövqelərdə x[1], x[2], ..., x[n] yerləşir. Əgər inək x mövqeyində r enerjisi ilə yerə düşərsə, bu, x − r ... x + r aralığında olan bütün ot tayalarının partlamasına səbəb olacaq "radiusu r" olan partlayışa səbəb olacaq. Bu aralıqdakı bütün ot tayaları eyni zamanda r − 1 partlayış radiusu ilə partlayır. Bu aralıqda hələ partlamamış ot tayaları yenidən r − 2 partlayış radiusu ilə partlayır və bu şəkildə davam edir.
İnəyin elə bir minimal enerji r ilə yerə düşməsini müəyyən edin ki, əgər o optimal mövqedə yerə düşərsə, səhnədəki bütün ot tayaları partlasın.
Giriş məlumatları
Birinci sətir n (2 ≤ n ≤ 50000) ehtiva edir. Qalan n sətir x[1] ... x[n] tam ədədlərini ehtiva edir (hər biri 0 ... 10^9 aralığında).
Çıxış məlumatları
İnəyin bütün ot tayalarını partlatmaq üçün yerə düşməli olduğu minimal enerjini R çıxarın. Cavabı yuvarlaqlaşdırın və bir onluq rəqəmlə çıxarın.
İzah
Bu nümunədə, inək 5 mövqeyində 3 enerjisi ilə yerə düşərsə, 3 və 8 mövqelərindəki ot tayalarının partlamasına səbəb olacaq, sonra partlayışlar 2 radiusu ilə 1 və 10 mövqelərini əhatə edəcək, bu da 1 radiusu ilə son ot tayasının 11 mövqeyində partlamasına səbəb olacaq, bu isə 0 radiusu ilə partlayır.