#761. 这是一道二分题

这是一道二分题

题目描述

到达目的地后,你想在新的星球上建立一个新的殖民地。由于这个星球上有很多山,而殖民地必须建在一个平坦的表面上,你决定用巨石把山压平(你还在做梦,所以这对你来说很有意义)。

你会得到一个数组h1,h2,...,hnh_1,h_2,...,h_n,其中hih_i是第ii座山的高度,kk--你拥有的巨石的数量。

你将从第一座山顶开始逐一投掷巨石,巨石的滚动情况如下(我们假设当前山的高度为hih_i)。

如果hihi+1h_i≥h_{i+1},巨石将滚到下一座山。

如果hi<hi+1h_i<h_{i+1},巨石将停止滚动并将山的高度增加11hi=hi+1h_i=h_i+1)。

如果巨石到达最后一座山,它将落入垃圾收集系统并消失。

你想找到第kk块巨石的位置或确定它将落入废物收集系统。

输入格式

第一行包含一个整数t1t100t(1≤t≤100)--测试案例的数量。

每个测试用例由两行组成。每个测试案例的第一行包含两个整数nnkk (1≤n≤100;1≤k≤10910^9)--山的数量和巨石的数量。

第二行包含n个整数h1,h2,...,hn1hi100h_1,h_2,...,h_n(1≤h_i≤100)--山的高度。

保证所有测试案例的n之和不超过100。

输出格式

对于每个测试案例,如果第kk块巨石将落入收集系统,则打印1-1。否则,打印第kk块巨石的位置。

样例

输入样例

4
4 3
4 1 2 3
2 7
1 8
4 5
4 1 2 3
3 1
5 3 1

输出样例

2
1
-1
-1

数据范围与提示

让我们模拟一下第一种情况。

第一块巨石从i=1开始;因为h1h2h_1≥h_2,所以它滚到i=2i=2,并在那里停下来,因为h2<h3h_2<h_3

新的高度是[4,2,2,3][4,2,2,3]

第二块巨石从i=1i=1开始;因为h1h2h_1≥h_2,所以巨石滚到i=2i=2;因为h2h3h_2≥h_3,所以巨石滚到i=3i=3,因为h3<h4h_3<h_4,所以停在那里。

新的高度是[4,2,3,3][4,2,3,3]

第三块巨石从i=1i=1开始;因为h1h2h_1≥h_2,所以它滚到i=2i=2,因为h2<h3h_2<h_3而停在那里。

新的高度是[4,3,3,3][4,3,3,3]

每块巨石停在的位置如下。

[2,3,2].[2,3,2].

在第二种情况下,所有77块巨石都将停在第一座山的右边,使其高度从11上升到88

第三种情况与第一种情况类似,但现在你要扔55块巨石。前三个将以与第一个测试案例相同的方式滚动。之后,山的高度将等于[4,3,3,3][4,3,3,3],这就是为什么另外两块巨石将落入收集系统。

在第四种情况下,第一块也是唯一的一块巨石将直接落入收集系统中。