Dwa termity postanowiły zjeść stary, drewniany płot. Płot ów składa się z n sztachet, których wysokości niekoniecznie są jednakowe. Termity pożarły już część z nich, ale stwierdziły, że warto tę pracę urozmaicić. Zdecydowały zagrać w grę i jeść na przemian po jednej sztachecie. Termit w przypadającej na niego kolejce może wybrać do zjedzenia tylko taką sztachetę, która sąsiaduje z jakąś wcześniej pożartą sztachetą. Wiedząc, że każdy z termitów tak wybiera sztachety, by w ciągu całej gry suma wysokości zjedzonych przez niego sztachet była jak największa, oblicz, ile drewna przypadnie każdemu z nich w udziale.
Wejście
W pierwszym wierszu standardowego wejścia znajduje się liczba całkowita n (1≤n≤1000000), określająca liczbę sztachet w płocie. Drugi wiersz zawiera ciąg n liczb całkowitych li (0≤li≤1000000000), opisujących wysokości kolejnych sztachet, przy czym 0 oznacza zjedzoną sztachetę. Sztacheta o numerze i (dla 1<i<n) sąsiaduje ze sztachetami o numerach i−1 oraz i+1, sztacheta o numerze 1 sąsiaduje tylko ze sztachetą o numerze 2, a sztacheta o numerze n tylko ze sztachetą o numerze n−1. Co najmniej jedna z liczb li na wejściu będzie równa zeru.
Wyjście
W pierwszym i jedynym wierszu standardowego wyjścia należy wypisać dwie liczby całkowite. Pierwsza z nich określa sumę wysokości sztachet, którymi pożywi się termit rozpoczynający rozgrywkę, zaś druga, ile drewna przypadnie jego przeciwnikowi.
Przykład
Dla danych wejściowych:
8
1 2 0 3 7 4 0 9
poprawną odpowiedzią jest:
17 9
Wyjaśnienie do przykładu: Płot składał się z 8 sztachet, z których 2 już są zjedzone. Pierwszy termit w pierwszym ruchu może wybrać sztachety o wysokościach 2, 3, 4 lub 9. W trakcie optymalnej rozgrywki jedzone będą kolejno sztachety o wysokościach 9, 2, 1, 4, 7 i 3.
Autor zadania: Tomasz Idziaszek.