解题思路

给定一个固定的交替串 s=1010...（长度为 n），每次操作任选一个相邻位置 i，若 s[i] != s[i+1] 就能删除这两位并得到积分 a[i]。题目特别强调数组 a 在整个过程中不变，每次选择第 i 位都获得同一个 a[i]，可以重复选择同一个下标（只要当时还满足 i < len(s)）。

关键性质

1. 始终可选：交替串删除任意相邻一对后仍是交替串，因此每一步对所有 1..len(s)-1 的 i 都满足 s[i] != s[i+1]。
2. 步数固定：每次删去 2 个字符，直到长度 ≤ 1，因此操作次数固定为 m = ⌊n/2⌋。
3. 可选区间单调缩小：第 1 步可选下标为 1..(n-1)，第 2 步为 1..(n-3)，……，第 k 步为

题目内容

TK 得到了一个神奇的字符串 $s$ (下标从 $1$ 开始)，该字符串长度为 $n$，仅由 {$'0’,'1’$} 构成，并且对于任意的下标 $i$ ,若 $i$ $mod$ $2=1$ ，则 $s_i ='1’$，否则 $s_i='0’$ 。

此外，给定一个长度为 $n-1$ 的整数数组 {$a_1,a_2,…,a_{n-1}$}。你可以重复进行如下操作，直到无法继续；

• 选择一个下标 $i(1 ≦i< len(s))$，且满足 $s_i ≠ s_{i+1}$ ; 获得积分 $a_i$ ;删除 $s_i$ 与 $s_{i+1}$，其余字符按原顺序拼接成新串。

注意，数组 $a$ 在整个过程中不发生变化：每次选择的位置 $i$ 始终对应同一个 $a_i$ ; 数组的长度与元素值均保持不变。

请分别求出完成全部操作后，累计积分的最大值与最小值。

输入描述

每个测试文件均包含多组测试数据。第一行输入一个整数 $T(1 ≦ T ≦ 10^4)$ 代表数据组数，每组测试数据描述如下：

• 第一行输入一个整数 $n(2 ≦n ≦ 2 × 10^5)$ 表示字符串长度;

• 第二行输入 $n -1$ 个整数 $a_1,a_2,...,a_{n-1}(1 ≦ a_i≦ 10^9)$ 表示奖励积分数组。

除此之外，保证单个测试文件的 $n$ 之和不超过 $2×10^5$ 。

输出描述

对于每一组测试数据，新起一行，输出两个整数：

第一个整数表示累计积分的最大值，第二个整数表示累计积分的最小值。

样例1

输入

2
4
5 1 4
3
7 2

输出

10 6
7 2

说明

对于第一组测试数据原字符串 $1010$ 最小值操作方式：

• 选择 $s_2,s_3$ 得到 $1$ 积分，字符串变为 $10$

• 选择 $s_1,s_2$ 得到 $5$ 积分，字符串变为空无法操作结束。

总共获得 $6$ 积分，可以证明不存在比此积分更小的操作方式。