假设你有一个数组。你可以进行任意次数（可能为零次）的以下操作：

• 选择数组中的一个元素，并删除该元素之前的所有元素，或该元素之后的所有元素（不包括该元素本身）。此操作的代价为所选元素的值。

数组的美观度是将数组大小减少到恰好为 $1$ 的操作序列的最小总代价。

给你一个由 $n$ 个整数组成的数组 $a$。在一秒内，你可以选择 $a$ 的两个相邻元素并交换它们。

你的任务是计算两个值：

• 你可以达到的 $a$ 的最大美观度；
• 达到该最大美观度所需的最少时间（秒数）。

输入格式

第一行包含一个整数 $t$ ($1 \le t \le 10^4$) —— 测试用例的数量。

每个测试用例包含两行：

• 第一行包含一个整数 $n$ ($2 \le n \le 3 \cdot 10^5$)。
• 第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$ ($1 \le a_i \le 10^9$)。

输入附加限制：所有测试用例中 $n$ 的总和不超过 $3 \cdot 10^5$。

输出格式

对于每个测试用例，输出两个整数 —— 数组可能达到的最大美观度，以及为了达到该最大美观度你必须花费的最少时间（以秒为单位）。

样例

输入样例 1

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

输出样例 1

2 0
1 0
3 3