Zostałeś wyznaczony do wyjątkowo trudnego zadania - podziału tortu pomiędzy trzy osoby.
Tort jest okrągły i należy go pociąć na trzy spójne kawałki prostymi cięciami od środka do obwodu. Na torcie leżą jednak gęsto poukładane różne owoce i ozdoby, dlatego ciąć można tylko w pewnych miejscach. Powinieneś tak rozdzielić tort, aby zminimalizować różnicę rozmiarów największego i najmniejszego kawałka. Uwaga! Nie są dopuszczalne podziały, w których ktoś nic nie dostanie.
W pierwszej linii wejścia podana jest jedna liczba całkowita 3 <= n <= 500 000, oznaczająca liczbę miejsc, w których można ciąć tort. Następnie jest n linijek, a w każdej jedna dodatnia liczba całkowita. Są to odstępy pomiędzy kolejnymi miejscami, w których można ciąć tort. Łączny obwód tortu (czyli suma tych n liczb) jest nie większy niż 1 000 000 000.
W pierwszej i jedynej linii wyjścia wypisz jedną liczbę całkowitą - minimalną różnicę pomiędzy długością największego i najmniejszego kawałka.
Dla danych
6 1 1 1 3 3 7
prawidłową odpowiedzią jest:
4
[Zgłoś rozwiązanie] [Moje zgłoszenia]