Codah ClubВежбај. Пошаљи. Напредуј.
Пријави се
Српски
#000276

Japanska buba

Japanska buba uletela je u pećinu punu prepreka: stalagmita (stoje na podu pećine) i stalaktita (vise sa plafona). Pećina je dužine N (gdje je N paran broj) i visine H. Prva prepreka je stalagmit, a zatim se smenjuju stalaktiti i stalagmiti.
Na slici je primer jedne pećine dužine 14 i visine 5 (slika odgovara drugom primeru test podataka):


Image: japanskabuba1

Japanskoj bubi se ne da izbegavati prepreke, nego odabere jednu od H nivoa i zaleti se s jednog kraja pećine na drugi, te svojim kung-fu veštinama poruši sve prepreke na putu. Na primer, ako u pećini sa prethodne slike odabere četvrti nivo od poda, onda će porušiti ukupno osam prepreka:


Image: japanskabuba2

U ovom primeru manje će se umoriti ako odabere prvi ili peti nivo, jer će u ta dva slučaja porušiti samo sedam prepreka. Zadane su dimenzije pećine i dužine svih prepreka. Napišite program koji određuje koliko najmanje prepreka buba mora porušiti da bi prošla na drugu stranu, te na koliko različitih nivoa se postiže ta najmanja vrijednost.


InputU prvom redu standardnog ulaza nalaze se prirodni brojevi N i H, 2 <= N <= 200 000, 2 <= H <= 500 000, dimenzije pećine. N će biti paran. Sledećih N redova sadrži redom dužine svih prepreka, prirodne brojeve manje od H.

OutputU prvi i jedini red standardnog izlaza izlazne ispišite dva cela broja odvojena jednim razmakom, najmanji broj prepreka koji buba mora porušiti te na koliko različitih nivoa se postiže ta najmanja vrednost.

Ulaz :
6 7
1
5
3
3
5
1
Izlaz :
2 3

Ulaz :
14 5
1
3
4
2
2
4
3
4
3
3
3
2
3
3

Izlaz:
7 2

Submit solution

Coming later

The grading service will be connected in a later migration step. You can inspect the task and your previous results now.