Sosial məsafə I
Yeni dəhşətli COWVID-19 xəstəliyi inəklər arasında yayılmağa başlayıb. Fermer Con, sürüsünü infeksiyadan qorumaq üçün mümkün qədər çox ehtiyat tədbirləri görməyə çalışır.
Fermer Conun tövləsi uzun, dar bir binadır və n sıradan ibarətdir. Bu tövlələrin bəziləri inəklərlə doludur, bəziləri isə boşdur. "Sosial məsafənin" əhəmiyyəti haqqında oxuduqdan sonra, fermer Con iki ən yaxın dolu tövlə arasındakı məsafəni, d-ni, maksimuma çatdırmaq istəyir. Məsələn, əgər 3 və 8 nömrəli tövlələr ən yaxın dolu tövlələrdirsə, onda d = 5.
Fermer Conun sürüsünə iki yeni inək qoşulub və o, bu inəklərin əvvəllər boş olan hansı tövlələrdə yerləşdirilməli olduğunu qərarlaşdırmalıdır. İki yeni inəyi elə yerləşdirin ki, nəticədə d mümkün qədər böyük olsun. Fermer Con mövcud inəkləri köçürə bilməz; o, yalnız yeni inəklər üçün tövlələr ayırmaq istəyir.
Giriş məlumatları
Birinci sətir n ədədini (2 ≤ n ≤ 10^5) ehtiva edir. Növbəti sətir tövlədəki tövlələrin ardıcıllığını təsvir edən uzunluğu n olan 0 və 1-lərdən ibarət bir sətir ehtiva edir. 0 boş tövlələri, 1 isə dolu tövlələri göstərir. Sətirdə həmişə ən azı iki 0 var, buna görə də iki yeni inək üçün həmişə yer var.
Çıxış məlumatları
Fermer Con iki yeni inəyi optimal şəkildə əlavə etdikdən sonra əldə edə biləcəyi ən böyük d (iki dolu tövlə arasındakı ən yaxın məsafə) dəyərini göstərin.
Nümunə
Fermer Con inəkləri elə əlavə edə bilər ki, sətir 10x010010x0010 formasını alsın, burada x yeni inəkləri göstərir. Bu halda d = 2. Daha yüksək d dəyərinə çatmaq üçün yeni inəkləri əlavə etmək mümkün deyil.