Żołnierze z całej bazy (bynajmniej nie chodzi o bazę danych!) spieszą się na apel. Powinni ustawić się na planie kwadratu, tak, żeby każdych dwóch żołnierzy mieszkających w tym samym budynku stało na apelu obok siebie, czyli w tym samym rzędzie kwadratu. Ponadto, żołnierze z poszczególnych budynków muszą stać po kolei, tzn. poczynając od pierwszego rzędu: pierwszy budynek, drugi budynek, itd. Pomóż znaleźć najmniejszą długość boku takiego kwadratu.
W pierwszym wierszu wejścia znajduje się jedna liczba całkowita n (1 <= n <= 500.000), oznaczająca liczbę budynków, w których mieszkają żołnierze. W kolejnych n wierszach znajdują się liczby żołnierzy zamieszkujących kolejne budynki. Liczba żołnierzy w każdym budynku jest dodatnia i nie większa niż 109.
Na wyjściu powinna znaleźć się dokładnie jedna liczba całkowita: najmniejsze k, takie że żołnierzy da się rozmieścić w k rzędach, w każdym rzędzie nie więcej niż k żołnierzy i tak, że jeśli dwaj żołnierze mieszkają w tym samym budynku, to stoją w tym samym rzędzie.
Dla danych wejściowych:
5 2 3 1 2 1
poprawnym wynikiem jest:
4
Przykład takiego rozstawienia żołnierzy: (każde A to żołnierz z pierwszego budynku, B - z drugiego, itd.)
AA** BBB* CDD* *E**Nie jest możliwa zamiana kolejności budynków, więc nie można ustawić żołnierzy w kwadrat o boku 3, np. tak:
AAE BBB CDD
[Zgłoś rozwiązanie] [Moje zgłoszenia]