Homie from Suomi

View as PDF

Submit solution

Points: 5
Time limit: 1.5s
Memory limit: 64M

Problem type

In the spirit of Finland Day, Kaarlo is visiting his friend in Oulu. As a proud Finn, Kaarlo is using Finland's national vehicle: skis. A common saying in Finland is to "test the ice with a stick before stepping on it", and Kaarlo is well aware of this rule.

Kaarlo departs from Helsinki and heads straight for Oulu. Along this distance, he gets several of his Finnish friends to test out the ice at every area with sticks. Using advanced Finnish technology, each friend reports an estimated thickness of the ice.

Kaarlo knows that it is dangerous to travel on thin ice, but he wants to go in a straight line to Oulu. He devises a plan: he uses his trusty chisel and shovel to collect ice from the thicker areas and moves them to the thinner areas. This, of course, means that he can only move ice from previously visited areas. When he is moving ice from the area a_i, he is considered to be still stepping on that area a_i. When he is moving ice to an area a_i, he is considered to be stepping on the area a_{i-1} which is right before it. Kaarlo starts at the 1^\text{st} area and must get to the N^\text{th} area. He must traverse across the areas one area at a time in order to get to Oulu. Kaarlo wants to make it to his friend in time for Finland Day, so he wants to move the minimum amount of ice necessary.

Kaarlo knows that he is light enough to safely step on ice that is at least M inches thick. At no point should he be stepping on an area with a thickness a_i in which a_i < M. Given the thickness reports of N areas along the way, determine the minimum amount of ice Kaarlo must move to make it to his friend safely.


1 \le N \le 10^6

1 \le M \le 1000

1 \le a_i \le 1000 for all 1 \le i \le N

Input Specification

The first line contains two integers N and M, the number of areas and minimum thickness respectively, separated by a space.

The next N lines contain an integer a_i representing the thickness in inches of the i^\text{th} area starting from Helsinki.

Output Specification

Output an integer representing the inches of ice Kaarlo must move. If it is impossible, output -1.

Sample Input

5 3

Sample Output



There are no comments at the moment.