题目描述
给定一个长度为 n 的数组 a,它是整数 0,1,…,n−1 的一个排列。你可以执行以下操作至多一次:
- 选择两个不同的下标 i 和 j(i=j),交换 ai 和 aj 的值。
执行操作后,定义 fi=mex(a1,a2,…,ai)。mex(c) 表示集合 c 的最小排除值(MEX)∗。
给定一个整数 k,找到在上述操作中使用的两个下标,使得 f1,f2,…,fn 中第 k 大的值最大化。如果不需要操作,输出 −1。
如果有多个合法答案,输出任意一个均可。
∗整数集合 c1,c2,…,ck 的最小排除值(MEX)定义为不在集合 c 中出现的最小非负整数 x。
输入格式
每个测试包含多个测试用例。第一行包含测试用例数 t(1≤t≤50)。随后是各测试用例的描述。
对于每个测试用例,第一行包含两个整数 n 和 k(2≤n≤100,1≤k≤n),其中 n 是数组 a 的元素个数,k 是要最大化的值的排名(k=1 对应最大值)。
下一行包含 n 个整数:a1,a2,…,an。保证 0,1,…,n−1 中的每个值在数组 a 中恰好出现一次。
保证所有测试用例的 n 之和不超过 100。
输出格式
对于每个测试用例,输出一行,包含在操作中使用的两个下标,以使 f1,f2,…,fn 中第 k 大的值最大化。如果不需要操作,输出 −1。
样例
3
5 1
0 1 2 3 4
3 2
2 0 1
5 2
0 2 1 4 3
-1
1 3
4 5
说明
在第一个测试用例中,不需要任何操作;f1,f2,…,f5 中第 1 大的值是 f5=5。实际上,如果执行交换操作,无论选择哪两个下标,f5 始终是最大的,值为 5。
在第二个测试用例中,交换 a1 和 a3 后,得到数组 [1,0,2],且 f1=0,f2=2,f3=3;f1,f2,f3 中第 2 大的值是 f2=2。
来源
导入自 Codeforces — Codeforces Round 1130 (Div. 2).