Homie from Suomi

View as PDF

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

Author:
Problem type
Allowed languages
Ada, Assembly, Awk, Brain****, C, C#, C++, COBOL, CommonLisp, D, Dart, F#, Forth, Fortran, Go, Groovy, Haskell, Intercal, Java, JS, Kotlin, Lisp, Lua, Nim, ObjC, OCaml, Octave, Pascal, Perl, PHP, Pike, Prolog, Python, Racket, Ruby, Rust, Scala, Scheme, Sed, Swift, TCL, Text, Turing, VB, Zig

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 , he is considered to be still stepping on that area . When he is moving ice to an area , he is considered to be stepping on the area which is right before it. Kaarlo starts at the st area and must get to 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 inches thick. At no point should he be stepping on an area with a thickness in which . Given the thickness reports of areas along the way, determine the minimum amount of ice Kaarlo must move to make it to his friend safely.

for all

Input Specification

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

The next lines contains an integer representing the thickness in inches of the 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
4
2
7
2
1

Sample Output

4

Comments

There are no comments at the moment.