题目描述

青青和宁宁正在一起玩硬币选择游戏。

初始时桌面上有n 枚硬币，每枚硬币有一个面额，我们使用a1,a2,⋯,an 分别代表第 1,2,⋯,n 枚硬币的面额。

他们还各有一个属于自己的钱包，初始时，钱包都是空的。

从青青开始，双方轮流操作。每次操作中，当前的操作者会从桌面上剩余的硬币中选择面值不超过当前自己钱包中硬币的总面额的硬币中面额最大的一枚硬币，把它从桌子上拿走，放到自己的钱包里。如果桌面上剩余的所有硬币面值都超过了自己钱包里已有硬币的总面额，那么选择剩余的所有硬币中面额最小的一个。

当桌面上没有硬币时，游戏结束。

请你分别求出，游戏结束后，青青和宁宁钱包里硬币的总面额。

输入格式

第一行为一个整数，代表初始时桌面上的硬币的数量 n。
第二行为 n 个整数a1,a2,⋯,an，分别代表第1,2,⋯,n 枚硬币的面额。。

输出格式

输出共一行两个整数，第一个整数表示青青最终钱包里的总面额，第二个整数表示 宁宁最终钱包里硬币的总面额，两个整数之间使用一个空格隔开。。

样例

样例 1

输入 # 1

2
3 2

输出 # 1

2 3