Rusiyanın yolları
Rusiya dünyanın ən böyük ölkəsidir. Sankt-Peterburqdan Vladivostoka qədər avtomobillə bütün ölkəni keçmək üçün çoxlu günlər tələb olunur. Yolda hər cür hadisə baş verə bilər, buna görə də bu uzun və mürəkkəb marşrut boyunca fasiləsiz əlaqə sisteminin yaradılması üçün dövlət proqramı qəbul edilib. Təkcə əlaqə deyil, həm də yolun texniki vəziyyətinə nəzarət etmək, lazım gəldikdə təcili tibbi yardım göstərmək və daha çox şey təmin etmək lazımdır. Bu proqram çox vacibdir və onun icrası üçün podratçı şirkətlər tapmaq lazımdır. Üstəlik, bu marşrutu xidmət edəcək bütün şirkətlərin bərabər uzunluqda sahələr alması vacibdir.
Bütün marşrut boyunca şəhərlər və kəndlər yerləşir və işlərin bərabər paylanması üçün ən ağıllı həll yolu - hər bir şirkətin bir yaşayış məntəqəsindən digərinə qədər marşrut boyunca bir sahə almasıdır. Bu sahənin içərisində digər yaşayış məntəqələri də ola bilər. Yaşayış məntəqələri arasındakı məsafələr məlumdur. Beləliklə, məsələni həll etmək üçün yaşayış məntəqələri arasındakı məsafələr ardıcıllığını elə bölmək lazımdır ki, hər bir sahə üçün şəhərlər arasındakı məsafələrin cəmləri eyni olsun. Şəkildə marşrutun belə bir bölünmə nümunəsi göstərilib.
Hökumət, hər bir şirkətə yerinə yetirilə bilən iş həcmi vermək üçün marşrutu elə bölmək istəyir ki, alınan sahələr minimal uzunluqda olsun. Sizin vəzifəniz belə bir həll tapmaqdır.
Giriş verilənləri
Giriş faylının birinci sətirində N - Peterburq-Vladivostok marşrutunda yaşayış məntəqələri arasındakı sahələrin sayı olan bir tam ədəd var. Sonra N tam ədədlər gəlir - yaşayış məntəqələri arasındakı məsafələr. Ədədlər boşluq və/və ya sətir keçidləri ilə ayrılmışdır (1 ≤ N ≤ 10000).
Çıxış verilənləri
Bir ədəd çıxarın - bir şirkətə xidmət etmək üçün tapşırılmalı olan marşrutun minimal uzunluğu.