链接：https://codeforces.com/problemset/problem/1682/C

题意：           时间1秒   范围  $t$ (1≤t≤10^4)      n (1≤n≤2⋅10^5) 

输入t组  长度为n的数列a。  

求该数列的LIS(a)  和 LIS(a’)    a'为数组a的翻转

求出 temp = min(LIS(a),LIS(a’) )

数列可以经过任意排列，  使这个temp 最大

思路：

通过输入的情况可以看到，最大大概是  2*10^9

我们处理起来也就是   10^4  *  （2*10^5   *    算法）

考虑  n  和  sqrt(n) 的算法

这样来看全排列应该是不能暴力的，找最长上升子序列是nlogn也不能用

算法最多就是搜一遍

通过题意我们可以看出，如果我们想使temp  最大，那么严格最长上升子序列和严格最长下降子序列应该尽量保持一致

假设出现的每一个数的次数都>=2，那么我们将两边排开   可以使两边的数量一致，剩下的数随便扔到两边

也就是说，如果对于任意cnt(ai) >=2  ，那么  temp = set(a).size()   

然后考虑单数情况，如果看出了上面的规律，这里我们不难考虑。如果一堆数出现的次数都是1，也就是他们互不相同。我们从中间开始，依次向两边放入两个剩下数中最大的数，cnt  为单数  ，temp = cnt/2向上取整

将两种情况合并就是最终答案

使用mapt记录  每个数出现的次数，然后用迭代器遍历一遍。这个复杂度在n以内

代码：

	#include<bits/stdc++.h>
	using namespace std;
	#define ll long long
	map<ll,ll>mapt;
	
	int main()
	{
		ll t ,n;
		cin>>t;
		while(t--)
		{
			ll k,cnt2=0,dcnt=0;
			cin>>n;
			for(ll i=1;i<=n;i++)
			{
				cin>>k;
				mapt[k]++;
			}
			for(auto it = mapt.begin();it!=mapt.end();it++)
			{
				if(it->second==1)
					dcnt++;
				if(it->second>=2)
					cnt2++;
			}
			if(dcnt%2==1)
				dcnt++;
		//	cout<<cnt2<<"~"<<dcnt<<endl;
			cout<<cnt2+dcnt/2<<endl;
			mapt.clear();
		}
	}