圈（cycle）是一个具有 $n$ 个顶点和 $n$ 条边的无向图，其中第 1 个顶点与第 2 个顶点之间有边，第 2 个顶点与第 3 个顶点之间有边，……，第 $(n-1)$ 个顶点与第 $n$ 个顶点之间有边，最后第 $n$ 个顶点与第 1 个顶点之间也有边。

两名玩家正在瓜分这个圈。第一名玩家首先任意选取一个顶点归自己所有。随后，第二名玩家可以选取任意其他顶点归自己所有。他们轮流进行，每回合选取一个尚未被选取的顶点。除第一回合外，玩家在每回合只能选取与自己之前已选取的至少一个顶点相连的顶点。当所有顶点都被选取后，游戏结束。

每个顶点都有一个关联的正整数值。每名玩家都试图最大化自己所选顶点的总价值。如果两名玩家都采取最优策略，最终每名玩家所选顶点的总价值分别是多少？

输入格式

输入文件的第一行包含整数 $n$ —— 顶点的数量，$3 \le n \le 10^6$。输入文件的第二行包含 $n$ 个以空格分隔的整数 —— 沿圈排列的顶点值，每个值在 $1$ 到 $10^9$ 之间。

输出格式

输出两个以空格分隔的整数：先手玩家最终将获得的顶点总价值，以及后手玩家最终将获得的顶点总价值。

样例

样例输入 1

4
1 2 3 4

样例输出 1

5 5