Islands


Submit solution

Points: 1 (partial)
Time limit: 2.0s
Memory limit: 512M

Author:
Problem types
Allowed languages
C, C++, Haskell, Java, Perl, Python

You have a cross section of an island. This is in the form of a histogram of heights at consecutive integer coordinates along the island. For example, it might be \(\{1, 3, 2\}\). This represents an island which has height 1 at the leftmost location, height 3 at the middle location, and height 2 at the rightmost location.

The sea level starts off at height 0 at time 0, but rises one unit of height per unit of time. You wonder what the earliest time is at which there are exactly \(X\) islands. For example, if our island is initial \(\{2,1,2\}\). At time 0, there is 1 island (our initial island), but at time 1, there are two islands (the two 2s), since the part of the island with height 1 becomes submerged. Note that, once the sea level is at height \(h\), any point on the island with height \(<=h\) is submerged.

To make it easier to work out, you want to write a program that takes an island of size \(N\), and a target number of islands \(X\), and outputs the first time at which there are exactly \(X\) islands.

Input Specification

The first line will contain a single integers, \(T\), the number of test cases to follow. Each test case has the following format. The first line will contain two space separated integers \(N\) and \(X\), the size of the initial island, and the target number of islands. The next line will contain \(N\) space separated integers, the \(i\)th of which we shall call \(h_i\).

Output Specification

For each test case, output a single integer on its own line. The first time there are exactly \(X\) islands. If there is no such time, output -1.

Bounds

\(1 \leq T \leq 100\)

\(1 \leq h_i \leq N\)

\(0 \leq X \leq N\)

Note this problem includes two sub-problems of increasing difficulty worth different numbers of points:

  • 20 points: \(1 \leq N \leq 100\)
  • 80 points: \(1 \leq N \leq 10000\)

Sample Input

2
5 2
2 3 2 3 2
5 1
3 3 2 3 3

Sample Output

2
0

Comments

There are no comments at the moment.