QOJ.ac

QOJ

Time Limit: 1 s Memory Limit: 256 MB
[0]

# 2103. Termity

统计

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 (1n1000000), określająca liczbę sztachet w płocie. Drugi wiersz zawiera ciąg n liczb całkowitych li (0li1000000000), 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 i1 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 n1. 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.