Воспитувачката во една градинка во слободно време е програмер. Таа работи со М деца. На час од физичка активност на децата им дала на располагање N различни топки (нумерирани со броеви од 1 до N). Секое дете земало одреден број на топки и притоа децата ги земале сите топки.

Бидејќи децата имаат различен број на топки кај нив, воспитувачката ги распоредила децата во еден ред по редослед според бројот на топки кои го имаат. Притоа, првото дете (тоа најлево) има најголем број на топки, а секое наредно има помал или еднаков број на топки во однос на претходното.

Воспитувачката си ја поставила следната задача:
Децата треба да си ги подаваат топките според нејзините наредби, така што на крај ќе се постигне да разликата меѓу бројот на топки кои ги имаат кои било две деца биде најмногу 1. Едно дете може да подава топка само на детето кое во редот е веднаш до него (лево или десно од него). Најважно, децата треба да ги подаваат топките на тој начин што секоја топка ќе биде подадена најмал број пати.

Воспитувачката напишала соодветен алгоритам и успешно го спровела. (Секоја наредба била отприлика ваква: „Бојан (или Ана, Трајче...) подај ја топката 4 на Диме...“.

При вака спроведен алгоритам, ваша задача е да пресметате, колку пати ќе биде подадена топката која е подадена најмногу пати?

Влез

Во првиот ред се запишани два броја M и N кои ги преставуваат бројот на деца и бројот на топки (0<= M <= 10 000, 0<=N <= 10 000 000) .

Во следниот ред се запишани M броеви А[i], i=1..M одделени со празно место. A[i] е бројот на топки кои ги има i-тото дете (0<= A[i] <= 1 000), дадени според редоследот како што децата се наредени во редот.

Излез

Колку пати ќе биде подадена топката која е подадена најмногу пати.

Ограничувања

Временско ограничување: 1 second
Мемориско ограничување: 64 megabytes

Примери

влез
3 6
3 2 1

излез
1

влез
3 4
2 2 0

излез
1

Објаснување за првиот тест пример: Првото дете подава една топка до второто дете. Со ова една од топките е подадена еднаш, а бројот на топки кои ги имаат децата во редослед како што се наредени во редот е: 2 3 и 1. Потоа, второто дете подава друга топка (не таа што ја добило од првото) до третото дете. Со тоа и оваа топка е подадена еднаш. По ова подавање сите деца имаат по две топки. Една топка е подадена најмногу еднаш.

Објаснување за вториот тест пример: Второто дете подава една топка на третото дете. Сега разликата на бројот на топки кои ги имаат кои било две деца е најмногу 1 (бројот на топки кои ќе ги имаат децата е: 2 1 1). Со тоа подавањето завршува. Една топка е подадена најмногу еднаш.