说明

有n个派,每个派有一个大小ai,
小A和小B有一个旗子,谁有旗子可以选择当前派给自己或对方,同时下一回合没有得到派的人将得到旗子,刚开始的时候小B拿着旗子
已知每个人都会选择最优的策略,小A和小B最终得到的派的体积分别是多少?

输入格式

第一行为一个正整数n代表派的个数  n <= 1e5
接下来一行为n个正整数 ，代表派的体积 ai <= 1e6

输出格式

输出为两个正整数，分别代表小A得到的最大体积和小B得到的最大体积。

样例

5
10 21 10 21 10

31 41