You may have heard of the pie rule before. It states that if two people wish to fairly share a slice of pie, one person should cut the slice in half, and the other person should choose who gets which slice. Alice and Bob have many slices of pie, and rather than cutting the slices in half, each individual slice will be eaten by just one person.
The way Alice and Bob decide who eats each slice is as follows. First, the order in which the pies are to be handed out is decided. There is a special token called the "decider" token, initially held by Bob. Until all the pie is handed out, whoever has the decider token will give the next slice of pie to one of the participants, and the decider token to the other participant. They continue until no slices of pie are left.
All of the slices are of excellent quality, so each participant obviously wants to maximize the total amount of pie they get to eat. Assuming both players make their decisions optimally, how much pie will each participant receive?
## Input
Input will begin with an integer _N_ (1 ≤ _N_ ≤ 50), the number of slices of pie.
Following this is a line with _N_ integers indicating the sizes of the slices (each between 1 and 100000, inclusive), in the order in which they must be handed out.
## Output
Print two integers. First, the sum of the sizes of slices eaten by Alice, then the sum of the sizes of the slices eaten by Bob, assuming both players make their decisions optimally.
[samples]
## Note
In the first example, Bob takes the size 141 slice for himself and gives the decider token to Alice. Then Alice gives the size 592 slice to Bob and keeps the decider token for herself, so that she can then give the size 653 slice to herself.
你可能听说过派规则。该规则指出，如果两个人希望公平地分享一块派，一个人负责将派切成两半，另一个人则选择拿哪一半。Alice 和 Bob 有很多片派，但他们并不将每片派切成两半，而是每片派将由其中一人完整吃掉。
Alice 和 Bob 决定谁吃每片派的方式如下：首先，决定派的分发顺序。有一个特殊的令牌称为“决定者”令牌，初始由 Bob 持有。在所有派分完之前，持有决定者令牌的人将下一片派分给其中一人，并将决定者令牌交给另一个人。他们持续此过程，直到所有派都被分完。
所有派片质量极佳，因此每位参与者显然都想最大化自己吃到的派的总量。假设两名玩家都做出最优决策，每人将各吃到多少派？
输入首先是一个整数 #cf_span[N] (#cf_span[1 ≤ N ≤ 50])，表示派片的数量。
接下来是一行包含 #cf_span[N] 个整数，表示每片派的大小（每个大小在 #cf_span[1] 到 #cf_span[100000] 之间，包含端点），按必须分发的顺序排列。
请输出两个整数：第一个是 Alice 吃到的派片大小之和，第二个是 Bob 吃到的派片大小之和，假设两名玩家都做出最优决策。
在第一个例子中，Bob 将大小为 #cf_span[141] 的派片留给自己，并将决定者令牌交给 Alice。接着，Alice 将大小为 #cf_span[592] 的派片给 Bob，自己保留决定者令牌，以便随后将大小为 #cf_span[653] 的派片留给自己。
## Input
输入首先是一个整数 #cf_span[N] (#cf_span[1 ≤ N ≤ 50])，表示派片的数量。接下来是一行包含 #cf_span[N] 个整数，表示每片派的大小（每个大小在 #cf_span[1] 到 #cf_span[100000] 之间，包含端点），按必须分发的顺序排列。
## Output
请输出两个整数：第一个是 Alice 吃到的派片大小之和，第二个是 Bob 吃到的派片大小之和，假设两名玩家都做出最优决策。
[samples]
## Note
在第一个例子中，Bob 将大小为 #cf_span[141] 的派片留给自己，并将决定者令牌交给 Alice。接着，Alice 将大小为 #cf_span[592] 的派片给 Bob，自己保留决定者令牌，以便随后将大小为 #cf_span[653] 的派片留给自己。
Let $ N $ be the number of pie slices, and let $ s_1, s_2, \dots, s_N $ be the sizes of the slices in the given order. Let $ A $ and $ B $ denote the total pie received by Alice and Bob, respectively. Initially, Bob holds the decider token.
At each step $ i \in \{1, \dots, N\} $, the player holding the decider token chooses:
- which of the two players receives slice $ s_i $, and
- who receives the decider token for the next step.
Both players act optimally to maximize their own total pie.
Define $ dp[i][p] $ as the maximum difference $ A - B $ that the current decider (player $ p $) can guarantee from step $ i $ to the end, where $ p = 0 $ denotes Alice holds the token, and $ p = 1 $ denotes Bob holds the token.
**Base case:**
$$
dp[N][p] = 0 \quad \text{for } p \in \{0,1\}
$$
**Recurrence:**
At step $ i $, if player $ p $ holds the decider token, they choose to assign slice $ s_i $ to either themselves or the opponent, and pass the token to the other. They choose the option that maximizes their advantage:
- If $ p = 0 $ (Alice has token):
$$
dp[i][0] = \max\left( s_i + dp[i+1][1],\ -s_i + dp[i+1][0] \right)
$$
(Assign $ s_i $ to Alice → +$ s_i $, token to Bob; or assign to Bob → -$ s_i $, token stays with Alice)
- If $ p = 1 $ (Bob has token):
$$
dp[i][1] = \max\left( s_i + dp[i+1][0],\ -s_i + dp[i+1][1] \right)
$$
(Assign $ s_i $ to Bob → +$ s_i $, token to Alice; or assign to Alice → -$ s_i $, token stays with Bob)
**Initial state:**
$ dp[0][1] $ (Bob starts with token)
Let $ D = dp[0][1] $. Then:
- $ A - B = D $
- $ A + B = \sum_{i=1}^N s_i = S $
Solving:
$$
A = \frac{S + D}{2}, \quad B = \frac{S - D}{2}
$$
**Output:** $ A $, $ B $
---
**Formal statement:**
Given:
- $ N \in \mathbb{Z}^+ $, $ 1 \leq N \leq 50 $
- $ s_1, s_2, \dots, s_N \in \mathbb{Z}^+ $, $ 1 \leq s_i \leq 100000 $
Define:
- $ S = \sum_{i=1}^N s_i $
- $ dp[i][p] $ for $ i \in \{0, \dots, N\} $, $ p \in \{0,1\} $:
$$
dp[N][p] = 0
$$
$$
dp[i][0] = \max(s_i + dp[i+1][1],\ -s_i + dp[i+1][0])
$$
$$
dp[i][1] = \max(s_i + dp[i+1][0],\ -s_i + dp[i+1][1])
$$
Compute:
- $ D = dp[0][1] $
- $ A = \frac{S + D}{2} $
- $ B = \frac{S - D}{2} $
Output: $ A $, $ B $