Pie Rules

파이 규칙에 대해 들어 본 적이 있을 것이다. 이 규칙에 따르면 두 사람이 파이 한 조각을 공평하게 나누어 먹으려면, 한 사람이 그 조각을 반으로 자르고 다른 사람이 어느 조각을 누가 받을지 정해야 한다. Alice and Bob에게는 파이 조각이 많이 있으며, 조각을 반으로 자르는 대신 각각의 조각을 단 한 사람만 먹는다.

Alice and Bob이 각 조각을 누가 먹을지 정하는 방법은 다음과 같다. 먼저 파이를 나누어 줄 순서를 정한다. "decider" 토큰이라는 특별한 토큰이 있으며, 처음에는 Bob이 가지고 있다. 모든 파이를 나누어 줄 때까지, 결정자 토큰을 가진 사람이 다음 파이 조각을 참가자 중 한 명에게 주고 결정자 토큰을 다른 참가자에게 준다. 남은 파이 조각이 없을 때까지 이 과정을 계속한다.

모든 조각의 품질이 훌륭하므로, 각 참가자는 당연히 자신이 먹게 되는 파이의 총량을 최대화하려 한다. 두 참가자가 모두 최적으로 결정한다고 가정할 때, 각 참가자는 얼마나 많은 파이를 받게 되는가?

입력은 파이 조각의 수를 나타내는 정수 N (1 ≤ N ≤ 50)로 시작한다.

그다음 줄에는 조각의 크기를 나타내는 N개의 정수가 반드시 나누어 주어야 하는 순서대로 주어진다(각 정수는 1 이상 100000 이하이다).

두 정수를 출력한다. 먼저 Alice가 먹은 조각들의 크기 합을 출력하고, 그다음 두 참가자가 모두 최적으로 결정한다고 가정할 때 Bob이 먹은 조각들의 크기 합을 출력한다.

첫 번째 예제에서 Bob은 크기가 141인 조각을 자신이 먹고 결정자 토큰을 Alice에게 준다. Then Alice은 크기가 592인 조각을 Bob에게 주고 결정자 토큰을 자신이 계속 가지고 있으며, 그 결과 이어서 크기가 653인 조각을 자신에게 줄 수 있다.