两只虫子决定吃掉一堵老旧的木栅栏。这堵栅栏由 $n$ 根木板组成，每根木板的高度不一定相同。虫子们从身边的白蚁朋友那里听说，有点良性的竞争会让进餐更加愉快。于是，它们决定玩个游戏，轮流吃掉木板。每轮中，轮到的虫子可以吃掉栅栏最边上的一根木板，或者同时吃掉两根最边上的木板。已知每只虫子都会尽可能让自己吃到的木板高度之和最大，请你计算最终每只虫子能吃到多少木头。

输入格式

输入的第一行包含一个整数 $n$（$1 \le n \le 1,000,000$），表示栅栏的木板数。第二行包含 $n$ 个整数 $h_{i}$（$1 \le h_{i} \le 1,000,000,000$），依次表示每根木板的高度。

输出格式

输出一行，包含两个整数。第一个整数表示率先开始游戏的虫子吃到的木板总高度，第二个整数表示它的对手吃到的木板总高度。

样例

输入

4
5 2 9 3

输出

14 5

说明

第一只虫子在第一步可以选择吃高度为 5 的木板、高度为 3 的木板，或者两根都吃。最优策略是只吃高度为 5 的木板。此时，第二只虫子会吃掉高度为 2 和 3 的两根木板。