나무좀

나무좀 두 마리가 낡은 나무 울타리를 갉아 먹기로 했다. 울타리는 널빤지 $n$개가 한 줄로 늘어선 것이며, 각 널빤지의 높이가 모두 같지는 않다. 식사를 더 즐겁게 하려고 두 나무좀은 이를 게임으로 만들어 번갈아 가며 널빤지를 먹기로 했다.

자기 차례가 된 나무좀은 현재 울타리의 양 끝에 있는 널빤지 중 하나(가장 왼쪽 또는 가장 오른쪽)를 먹거나, 양 끝의 널빤지 두 개를 한 번에 먹을 수 있다. 각 나무좀은 게임이 끝날 때까지 자신이 먹은 널빤지 높이의 합이 최대가 되도록 언제나 최선의 선택을 한다.

첫 번째 나무좀이 먼저 시작한다. 두 나무좀이 각각 먹게 되는 나무의 양을 구하여라.

첫째 줄에 널빤지의 개수 $n$ ($1 \le n \le 10^6$)이 주어진다.

둘째 줄에 왼쪽부터 오른쪽 순서로 각 널빤지의 높이 $h_1, h_2, \dots, h_n$ ($1 \le h_i \le 10^9$)이 주어진다.

한 줄에 정수 두 개를 출력한다. 먼저 게임을 시작한 나무좀이 먹은 널빤지 높이의 합을, 그다음 상대 나무좀이 먹은 높이의 합을 출력한다.

울타리 $5\ 2\ 9\ 3$을 생각해 보자. 첫 차례에 시작하는 나무좀은 높이 $5$인 널빤지, 높이 $3$인 널빤지, 또는 양 끝 두 개를 한 번에 먹을 수 있다. 높이 $5$를 먹는 것이 최적이다. 그러면 상대는 $2\ 9\ 3$을 마주하게 되고, 양 끝($2$와 $3$)을 한 번에 먹어 가운데 $9$를 남긴다. 결국 시작한 나무좀은 $5+9=14$를, 상대는 $2+3=5$를 먹는다.