样例下载

题目描述

Farmer John 有 $N$ 头奶牛，编号为 $1$ ~ $N$。奶牛 $i$ 的身高为 $H_i$。

John 想把这些奶牛从矮到高排序。他使用的排序方法是选择排序，即每次从还未排序的奶牛中选出身高最矮的奶牛，将该奶牛添加到已排序奶牛队伍的末端。从一堆奶牛中选出最矮的奶牛是比较费时的，John 从 $t$ 头奶牛中选出最矮的奶牛需要花费 $t$ 个时间单位。当 John 选出最矮的奶牛后，他会立刻将该头奶牛添加到队伍末端。

但是这样排序太慢了，于是 John 找来了他的好朋友 Jack 帮忙。John 会把若干头（可以是 $0$ 头，也可以是全部 $N$ 头）奶牛分给 Jack。

对于仍然留给自己的奶牛，John 仍按照他自己的排序方法进行排序。

而 Jack 的排序方法则非常奇特。对于一头身高为 $h$ 的奶牛，他会在第 $h$ 个时刻将该头奶牛添加到已排序奶牛队伍的末端。如果有多头身高相同的奶牛，则这些奶牛会被同时添加到队伍末端。

如果 John 和 Jack 同时向队伍末端添加奶牛，则 John 的奶牛将会先添加，Jack 的奶牛会被后添加。

添加奶牛是瞬间完成的，时间忽略不计。

分配完奶牛后，计时开始，Jack 和 John 便立刻开始按各自的排序方法对奶牛进行排队。

问：如何分配奶牛，可以使得全部排好队所需时间最短？你只需要输出排好队所需要的最短时间。

多组数据。

输入格式

第一行：一个整数 $T$，表示数据组数。

对于每组数据：

• 第一行：一个整数 $N$。
• 第二行：$N$ 个整数 $H_i$

数据保证所有组数据的 $\sum N ≤ 2·10^5$。

输出格式

共 $T$ 行，每组数据的答案占一行。

输入样例

3
3
10 20 30
4
1 5 5 5
5
1 2 3 4 100

输出样例

6
5
6

样例解释

每组数据的分配方案不一定唯一，以下仅列出一种可能方案：

第一组数据：John 全部自己完成。

第二组数据：全部分给 Jack 完成。

第三组数据：John 对 3, 4, 100 进行排序，将 1, 2 分给 Jack。具体过程如下：

时刻	被添加的奶牛
$1$	Jack 将奶牛 $1$（身高 $1$） 添加到队伍末端，John 正在挑选奶牛
$2$	Jack 将奶牛 $2$（身高 $2$） 添加到队伍末端，John 正在挑选奶牛
$3$	John 将奶牛 $3$（身高 $3$） 添加到队伍末端
$4$	John 正在挑选奶牛
$5$	John 将奶牛 $4$（身高 $4$） 添加到队伍末端
$6$	John 将奶牛 $5$（身高 $100$）添加到队伍末端

数据范围

• 10% 的数据：$N ≤ 16$。
• 25% 的数据：$N ≤ 150$。
• 45% 的数据：$\sum N ≤ 5000$。
• 100% 的数据：$1 ≤ T ≤ 10$; $1 ≤ \sum N ≤ 2·10^5$; $1 ≤ H_i ≤ 10^{11}$。