最近哪吒之魔童闹海十分火爆，小劉打算和他的朋友小🐏一起去观看，入场前他们想买爆米花吃。

题目描述

一桶爆米花有大有小，我们用正整数来表示爆米花的重量，在这里爆米花越重则爆米花体积越大，数字越大表示的爆米花越重。

小劉和他的朋友因为缺钱，所以他们只买了一桶爆米花，然后他们又拿了两个空的爆米花桶，打算将买的一桶爆米花分成两份，用来看电影的时候吃。

一桶爆米花 n 颗，小劉和他的朋友小🐏商量将n颗爆米花一字排开，可以从两端任意一端取，然后一人取一颗，小劉取去，然后小🐏再取。小劉比较喜欢大的爆米花，所以每次都会取较大一端的爆米花，若两端相同则取左边；然后小🐏不喜欢大的，也不喜欢小的，他只希望自己最后能够拿到重量更多的爆米花。

现在请你帮助小劉和小🐏取爆米花，分别输出小劉和小🐏最后能够取得爆米花的重量。

输入描述

每组测试数据描述如下：

第一行一个正整数 n ( 1 <= n <= 10³ ）表示爆米花的个数。

第二行一共 n 个正整数表示每个一字排开后的爆米花的大小 ( 1 <= 每个爆米花的大小 <= 10⁶ )。

输出描述

分别输出小劉和小🐏最后能够取得爆米花的重量。

样例

6
1 100 1 100 1 100

300 3

6
1 2 3 4 5 6

12 9

解释

对于第二个样例 小劉先取6，小🐏取5，小劉取4，小🐏取3，小劉取2，小🐏取1。

限制范围

每个测试样例限制为1s, 248Mb。