题目描述
三角形数组对于任意的数组取i,,j,k(1<=i,j,k<=n,i,j,k互不相等)使其代表的a[i],a[j],a[k]能够构成一个三角形，许宝宝非常喜欢三角形，许宝宝出去觅食的时候，他得到了一个数组，许宝宝想要这个数组变为三角形数组，因为许宝宝因为是宝宝，他有一项超能力即把i位置上的数字变为和j位上的数字相同的超能力(即a[i]=a[j])，但是使用多了超能力王哥哥会不开心，请问许宝宝最少使用多少次超能力，才能使整个数组都变为他喜欢的三角形数组。
输入
每个测试由多个测试用例组成。第一行包含一个整数 t(1≤t≤10000) - 测试用例数。测试用例说明如下. 每个测试用例的第一行包含一个整数 n(3≤n≤200000) - 数组 a中的元素个数。每个测试用例的第二行包含 n 个整数 a1,a2,…,an0(1≤ai≤1000000000) - 数组 a中的元素。 保证所有测试用例中 n 的总和不超过 200000 。
输出
对于每个测试用例，输出一个整数 - 许宝宝所需的最少操作数。
4
7
1 2 3 4 5 6 7
3
1 3 2
3
4 5 3
15
9 3 8 1 6 5 3 8 2 1 4 2 9 4 7