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 \le n \le 1\,000\,000$), określająca liczbę sztachet w płocie. Drugi wiersz zawiera ciąg $n$ liczb całkowitych $l_i$ ($0 \le l_i \le 1\,000\,000\,000$), 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 $l_i$ 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.