Гледката от прозореца на Ели към Витоша става все по-лоша в следствие на все по-високите сгради, които се строят между нея и планината. Те скриват по-долните части от Витоша, като потенциално планината загубва своята цялост - почват да се виждат само някои от по-високите части (върховете, например), но връзката между тях вече е скрита. В следствие на това, от гледна точка на Ели, можем да ги считаме за отделни, по-малки планинки. Разбира се, тяхната красота изобщо не може да се сравнява с това да гледаш величието на огромна планина пред себе си.

Момичето е "картографирало" височината на планината, гледана от нейния прозорец, като поредица от N числа H₁, H₂, ..., H_N - височината, измерена в някакви равни интервали. Построявайки сграда с височина X, частта от планината, която остава видима за Ели става с височини H₁ - X, H₂ - X, ..., H_N - X, като ако някое от тях стане нула или по-малко, момичето спира да вижда този нейн участък. В момента, в който престане да има поредица от K последователни участъка, които Ели вижда, тя счита, че всичко е загубено, и почва да си търси нов апартамент.

Помогнете на момичето, като изчислите кое е най-малкото X, при което не остава интервал от стриктно положителни числа H_i - X, H_i+1 - X, ..., H_i+K-1 - X. На първия ред на стандартния вход ще бъдат зададени целите числа N и K - съответно броя участъци на планината, както и най-късата дължина на интервал от планината, която Ели все още би счела за красива. На втория ред, разделени с интервали, ще бъдат зададени N цели числа H₁, H₂, ..., H_N - височината на планината, както момичето я вижда в момента от прозореца си. На единствен ред на стандартния изход изведете едно цяло число - минималното X, за което от планината няма да остане видим интервал с дължина по-голяма или равна на K.

• 1 ≤ K ≤ N ≤ 100,000
• 1 ≤ H_i ≤ 1,000,000,000

Примерен Вход	Примерен Изход
5 2 16 11 13 17 9	13
15 5 192 129 160 196 187 147 142 172 161 164 108 153 138 167 119	142