题目描述

给定一个长度为 $n$ 的非负整数序列 $a_1,a_2,\cdots a_n$。你可以使用一种操作：选择在序列中连续的两个正整数， 并使它们分别减一。当你不能继续操作时游戏结束，而你的得分等于你使用的操作次数。你的任务是计算可能 的最小得分和最大得分。

输入格式

第一行包含一个正整数 $T$ ，表示有 $T$ 组数据。

接下来依次给出每组测试数据。对于每组测试数据：

第一行包含一个正整数 $n$。

第二行包含 $n$ 个非负整数，表示 $a_1,a_2,\cdots a_n$。

约 $5$ 组数据满足 $n \ge 10^3$ 或 $\sum a_i \ge 10^4$。

输出格式

对于每组测试数据，输出一行两个非负整数，用一个空格隔开，前者表示可能的最小得分，后者表示可能的最大得分。

样例输入

2
4
1 2 1 3
5
1 2 1 1 3

样例输出

2 2
2 3

数据范围与约定

对于 $100\%$ 的数据，$1 \le n \le 10^5$ ， $1\le T \le 200$，$0\le \sum a_i \le 10^6$。

题目来源

鸣谢 Tangjz 提供试题