흰개미

흰개미 두 마리가 오래된 나무 울타리를 갉아 먹고 있다. 울타리는 높이가 서로 다를 수 있는 널빤지 $n$개로 이루어져 있으며, 그중 일부는 이미 갉아 먹혀 사라졌다. 두 흰개미는 번갈아 가며 한 번에 널빤지 하나씩을 먹는다. 자기 차례에는 이미 먹힌 널빤지와 바로 옆에 붙어 있는 널빤지만 먹을 수 있다.

각 흰개미는 게임이 끝날 때까지 자신이 먹는 널빤지 높이의 합이 최대가 되도록 움직인다. 두 흰개미가 각각 먹게 되는 나무의 양을 구하여라.

첫째 줄에 널빤지의 개수 $n$이 주어진다 ($1 \le n \le 1{,}000{,}000$).

둘째 줄에 널빤지의 높이를 나타내는 정수 $n$개 $l_1, l_2, \dots, l_n$이 공백으로 구분되어 주어진다 ($0 \le l_i \le 1{,}000{,}000{,}000$). $l_i = 0$이면 $i$번째 널빤지는 이미 먹힌 상태이다. $1 < i < n$인 널빤지 $i$는 널빤지 $i-1$, $i+1$과 이웃한다. 널빤지 $1$은 널빤지 $2$와만, 널빤지 $n$은 널빤지 $n-1$과만 이웃한다. $l_i$ 중 적어도 하나는 $0$이다.

한 줄에 정수 두 개를 출력한다. 첫 번째 정수는 게임을 먼저 시작하는 흰개미가 먹는 널빤지 높이의 합이고, 두 번째 정수는 상대 흰개미가 먹는 높이의 합이다.

샘플에서 울타리는 널빤지 8개로 이루어져 있고 그중 2개는 이미 먹힌 상태이다. 첫 번째 흰개미는 첫 차례에 높이 $2, 3, 4, 9$인 널빤지 중에서 고를 수 있다. 최적으로 진행하면 두 흰개미는 차례대로 높이 $9, 2, 1, 4, 7, 3$인 널빤지를 먹게 된다.