#NC14669. 栗酱的文明2

栗酱的文明2

题目描述

“伟大的勇栗兔栽栗女王,所有栗子看到您都不寒而栗,但也非常尊重您。您骑着威风凛凛的小白兔,带领栗子们奋勇前行。伟大史诗告诉我们,烈兔勇栗从大草原飞奔出来,

冲在每场战争的前线——无论您在哪里,他们都能找到您。骑小白兔飞驰吧,凶猛的女王,但愿您有真正的朋友和软弱的敌人。”

今天,冰雪聪明的栗酱终于玩到了她梦寐很久的文明游戏。

不过作为一个萌新,兔头獐脑的栗酱自然不愿意第一次玩就遇到一个尴尬的结局,于是希望通过你来寻找一个完美结局。

已知游戏结束前场上有n个国家,第i个国家有ai块土地,任意2个国家若是想建立外交关系,则需要互相在对方的一块土地上建立一个大使馆。

一块土地只能建立一个大使馆,若一个国家和其他国家存在外交关系,则需要征用一块己方土地作为备用大使馆。

完美结局的定义是:找到最多数量的国家,使他们相互之间存在外交关系。

输入格式

第一行一个数T,表示有T组数据。

对于每组数据,第一行输入一个数n,表示国家的数量,接下来一行输入n个数,a1,a2,…,an,其中ai表示第i个国家拥有的土地数量。每两个相邻的数之间用空格隔开。

输出格式

对于每一个询问,输出一个数,即完美结局下,相互建立外交关系的国家数量。答案至少是1。

提示

T≤10

1≤n≤1000

1≤ai≤n

样例 1

2
5
2 2 2 2 2
10
8 6 5 9 2 7 10 3 3 9
2
6

样例说明

对于第一个样例:

最多只能找到2个国家,使他们互相建立外交关系。

对于第二个样例:

第1,2,4,6,7,10个国家间可互相建立外交关系,最多数量为6。

来源

牛客原题