## Islands

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.