시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 128 MB103774272316842.541%

문제

개똥벌레 한 마리가 장애물(석순과 종유석)로 가득찬 동굴에 들어갔다. 동굴의 길이는 N미터이고, 높이는 H미터이다. (N은 짝수) 첫 번째 장애물은 항상 석순이고, 그 다음에는 종유석과 석순이 번갈아가면서 등장한다.

아래 그림은 길이가 14미터이고 높이가 5미터인 동굴이다. (예제 그림)

이 개똥벌레는 장애물을 피하지 않는다. 자신이 지나갈 구간을 정한 다음 일직선으로 지나가면서 만나는 모든 장애물을 파괴한다.

위의 그림에서 4번째 구간으로 개똥벌레가 날아간다면 파괴해야하는 장애물의 수는 총 여덟개이다. (4번째 구간은 길이가 3인 석순과 길이가 4인 석순의 중간지점을 말한다)

하지만, 첫 번째 구간이나 다섯 번째 구간으로 날아간다면 개똥벌레는 장애물 일곱개만 파괴하면 된다.

동굴의 크기와 높이, 모든 장애물의 크기가 주어진다. 이때, 개똥벌레가 파괴해야하는 장애물의 최솟값과 그러한 구간이 총 몇 개 있는지 구하는 프로그램을 작성하시오.

입력

첫째 줄에 N과 H가 주어진다. N은 항상 짝수이다. (2 ≤ N ≤ 200,000, 2 ≤ H ≤ 500,000)

다음 N개 줄에는 장애물의 크기가 순서대로 주어진다. 장애물의 크기는 H보다 작은 양수이다.

출력

첫째 줄에 개똥벌레가 파괴해야 하는 장애물의 최솟값과 그러한 구간의 수를 공백으로 구분하여 출력한다.

예제 입력 1

6 7
1
5
3
3
5
1

예제 출력 1

2 3

예제 입력 2

14 5
1
3
4
2
2
4
3
4
3
3
3
2
3
3

예제 출력 2

7 2
W3sicHJvYmxlbV9pZCI6IjMwMjAiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWFjMWNcdWI2MjVcdWJjOGNcdWI4MDgiLCJkZXNjcmlwdGlvbiI6IjxwPlx1YWMxY1x1YjYyNVx1YmM4Y1x1YjgwOCBcdWQ1NWMgXHViOWM4XHViOWFjXHVhYzAwIFx1YzdhNVx1YzU2MFx1YmIzYyhcdWMxMWRcdWMyMWNcdWFjZmMgXHVjODg1XHVjNzIwXHVjMTFkKVx1Yjg1YyBcdWFjMDBcdWI0ZGRcdWNjMmMgXHViM2Q5XHVhZDc0XHVjNWQwIFx1YjRlNFx1YzViNFx1YWMxNFx1YjJlNC4gXHViM2Q5XHVhZDc0XHVjNzU4IFx1YWUzOFx1Yzc3NFx1YjI5NCBOXHViYmY4XHVkMTMwXHVjNzc0XHVhY2UwLCBcdWIxOTJcdWM3NzRcdWIyOTQgSFx1YmJmOFx1ZDEzMFx1Yzc3NFx1YjJlNC4gKE5cdWM3NDAgXHVjOWRkXHVjMjE4KSBcdWNjYWIgXHViYzg4XHVjOWY4IFx1YzdhNVx1YzU2MFx1YmIzY1x1Yzc0MCBcdWQ1NmRcdWMwYzEgXHVjMTFkXHVjMjFjXHVjNzc0XHVhY2UwLCBcdWFkZjggXHViMmU0XHVjNzRjXHVjNWQwXHViMjk0IFx1Yzg4NVx1YzcyMFx1YzExZFx1YWNmYyBcdWMxMWRcdWMyMWNcdWM3NzQgXHViYzg4XHVhYzA4XHVjNTQ0XHVhYzAwXHViYTc0XHVjMTFjIFx1YjRmMVx1YzdhNVx1ZDU1Y1x1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVjNTQ0XHViNzk4IFx1YWRmOFx1YjliY1x1Yzc0MCBcdWFlMzhcdWM3NzRcdWFjMDAgMTRcdWJiZjhcdWQxMzBcdWM3NzRcdWFjZTAgXHViMTkyXHVjNzc0XHVhYzAwIDVcdWJiZjhcdWQxMzBcdWM3NzggXHViM2Q5XHVhZDc0XHVjNzc0XHViMmU0LiAoXHVjNjA4XHVjODFjIFx1YWRmOFx1YjliYyk8XC9wPlxyXG5cclxuPHAgc3R5bGU9XCJ0ZXh0LWFsaWduOiBjZW50ZXI7XCI+PGltZyBhbHQ9XCJcIiBzcmM9XCJodHRwczpcL1wvdXBsb2FkLmFjbWljcGMubmV0XC9jNmZkNDk2ZC1jY2Y1LTRmOWQtYTA2ZS0zMmIxMjFmYzZhODJcLy1cL3ByZXZpZXdcL1wiIHN0eWxlPVwid2lkdGg6IDI3MXB4OyBoZWlnaHQ6IDEwOHB4O1wiIFwvPjxcL3A+XHJcblxyXG48cD5cdWM3NzQgXHVhYzFjXHViNjI1XHViYzhjXHViODA4XHViMjk0IFx1YzdhNVx1YzU2MFx1YmIzY1x1Yzc0NCBcdWQ1M2NcdWQ1NThcdWM5YzAgXHVjNTRhXHViMjk0XHViMmU0LiBcdWM3OTBcdWMyZTBcdWM3NzQgXHVjOWMwXHViMDk4XHVhYzA4IFx1YWQ2Y1x1YWMwNFx1Yzc0NCBcdWM4MTVcdWQ1NWMgXHViMmU0XHVjNzRjIFx1Yzc3Y1x1YzljMVx1YzEyMFx1YzczY1x1Yjg1YyBcdWM5YzBcdWIwOThcdWFjMDBcdWJhNzRcdWMxMWMgXHViOWNjXHViMDk4XHViMjk0IFx1YmFhOFx1YjRlMCBcdWM3YTVcdWM1NjBcdWJiM2NcdWM3NDQgXHVkMzBjXHVhZDM0XHVkNTVjXHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWM3MDRcdWM3NTggXHVhZGY4XHViOWJjXHVjNWQwXHVjMTFjIDRcdWJjODhcdWM5ZjggXHVhZDZjXHVhYzA0XHVjNzNjXHViODVjIFx1YWMxY1x1YjYyNVx1YmM4Y1x1YjgwOFx1YWMwMCBcdWIwYTBcdWM1NDRcdWFjMDRcdWIyZTRcdWJhNzQgXHVkMzBjXHVhZDM0XHVkNTc0XHVjNTdjXHVkNTU4XHViMjk0IFx1YzdhNVx1YzU2MFx1YmIzY1x1Yzc1OCBcdWMyMThcdWIyOTQgXHVjZDFkIFx1YzVlY1x1YjM1Zlx1YWMxY1x1Yzc3NFx1YjJlNC4gKDRcdWJjODhcdWM5ZjggXHVhZDZjXHVhYzA0XHVjNzQwIFx1YWUzOFx1Yzc3NFx1YWMwMCAzXHVjNzc4IFx1YzExZFx1YzIxY1x1YWNmYyBcdWFlMzhcdWM3NzRcdWFjMDAgNFx1Yzc3OCBcdWMxMWRcdWMyMWNcdWM3NTggXHVjOTExXHVhYzA0XHVjOWMwXHVjODEwXHVjNzQ0IFx1YjlkMFx1ZDU1Y1x1YjJlNCk8XC9wPlxyXG5cclxuPHAgc3R5bGU9XCJ0ZXh0LWFsaWduOiBjZW50ZXI7XCI+PGltZyBhbHQ9XCJcIiBzcmM9XCJodHRwczpcL1wvdXBsb2FkLmFjbWljcGMubmV0XC9iZmNiYjk0Zi0wZTE1LTRmZjktYjJlZi00M2UwN2M3ZWU1MDNcLy1cL3ByZXZpZXdcL1wiIHN0eWxlPVwid2lkdGg6IDI5MnB4OyBoZWlnaHQ6IDEwOHB4O1wiIFwvPjxcL3A+XHJcblxyXG48cD5cdWQ1NThcdWM5YzBcdWI5Y2MsIFx1Y2NhYiBcdWJjODhcdWM5ZjggXHVhZDZjXHVhYzA0XHVjNzc0XHViMDk4IFx1YjJlNFx1YzEyZiBcdWJjODhcdWM5ZjggXHVhZDZjXHVhYzA0XHVjNzNjXHViODVjIFx1YjBhMFx1YzU0NFx1YWMwNFx1YjJlNFx1YmE3NCBcdWFjMWNcdWI2MjVcdWJjOGNcdWI4MDhcdWIyOTQgXHVjN2E1XHVjNTYwXHViYjNjIFx1Yzc3Y1x1YWNmMVx1YWMxY1x1YjljYyBcdWQzMGNcdWFkMzRcdWQ1NThcdWJhNzQgXHViNDFjXHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWIzZDlcdWFkNzRcdWM3NTggXHVkMDZjXHVhZTMwXHVjNjQwIFx1YjE5Mlx1Yzc3NCwgXHViYWE4XHViNGUwIFx1YzdhNVx1YzU2MFx1YmIzY1x1Yzc1OCBcdWQwNmNcdWFlMzBcdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiBcdWM3NzRcdWI1NGMsIFx1YWMxY1x1YjYyNVx1YmM4Y1x1YjgwOFx1YWMwMCBcdWQzMGNcdWFkMzRcdWQ1NzRcdWM1N2NcdWQ1NThcdWIyOTQgXHVjN2E1XHVjNTYwXHViYjNjXHVjNzU4IFx1Y2Q1Y1x1YzE5Zlx1YWMxMlx1YWNmYyBcdWFkZjhcdWI3ZWNcdWQ1NWMgXHVhZDZjXHVhYzA0XHVjNzc0IFx1Y2QxZCBcdWJhODcgXHVhYzFjIFx1Yzc4OFx1YjI5NFx1YzljMCBcdWFkNmNcdWQ1NThcdWIyOTQgXHVkNTA0XHViODVjXHVhZGY4XHViN2E4XHVjNzQ0IFx1Yzc5MVx1YzEzMVx1ZDU1OFx1YzJkY1x1YzYyNC48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlx1Y2NhYlx1YzlmOCBcdWM5MDRcdWM1ZDAgTlx1YWNmYyBIXHVhYzAwIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gTlx1Yzc0MCBcdWQ1NmRcdWMwYzEgXHVjOWRkXHVjMjE4XHVjNzc0XHViMmU0LiAoMiAmbGU7IE4gJmxlOyAyMDAsMDAwLCAyICZsZTsgSCAmbGU7IDUwMCwwMDApPFwvcD5cclxuXHJcbjxwPlx1YjJlNFx1Yzc0YyBOXHVhYzFjIFx1YzkwNFx1YzVkMFx1YjI5NCBcdWM3YTVcdWM1NjBcdWJiM2NcdWM3NTggXHVkMDZjXHVhZTMwXHVhYzAwIFx1YzIxY1x1YzExY1x1YjMwMFx1Yjg1YyBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIFx1YzdhNVx1YzU2MFx1YmIzY1x1Yzc1OCBcdWQwNmNcdWFlMzBcdWIyOTQgSFx1YmNmNFx1YjJlNCBcdWM3OTFcdWM3NDAgXHVjNTkxXHVjMjE4XHVjNzc0XHViMmU0LjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlx1Y2NhYlx1YzlmOCBcdWM5MDRcdWM1ZDAgXHVhYzFjXHViNjI1XHViYzhjXHViODA4XHVhYzAwIFx1ZDMwY1x1YWQzNFx1ZDU3NFx1YzU3YyBcdWQ1NThcdWIyOTQgXHVjN2E1XHVjNTYwXHViYjNjXHVjNzU4IFx1Y2Q1Y1x1YzE5Zlx1YWMxMlx1YWNmYyBcdWFkZjhcdWI3ZWNcdWQ1NWMgXHVhZDZjXHVhYzA0XHVjNzU4IFx1YzIxOFx1Yjk3YyBcdWFjZjVcdWJjMzFcdWM3M2NcdWI4NWMgXHVhZDZjXHViZDg0XHVkNTU4XHVjNWVjIFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIwIiwiaHRtbF90aXRsZSI6IjAiLCJwcm9ibGVtX2xhbmdfdGNvZGUiOiJLb3JlYW4ifSx7InByb2JsZW1faWQiOiIzMDIwIiwicHJvYmxlbV9sYW5nIjoiMSIsInRpdGxlIjoiRklSRUZMWSIsImRlc2NyaXB0aW9uIjoiPHA+QSBKYXBhbmVzZSBmaXJlZmx5IGhhcyBmbG93biBpbnRvIGEgY2F2ZSBmdWxsIG9mIG9ic3RhY2xlczogc3RhbGFnbWl0ZXMgKHJpc2luZyBmcm9tIHRoZSBmbG9vcikgYW5kIHN0YWxhY3RpdGVzIChoYW5naW5nIGZyb20gdGhlIGNlaWxpbmcpLiBUaGUgY2F2ZSBpcyBOIHVuaXRzIGxvbmcgKHdoZXJlIE4gaXMgZXZlbikgYW5kIEggdW5pdHMgaGlnaC4gVGhlIGZpcnN0IG9ic3RhY2xlIGlzIGEgc3RhbGFnbWl0ZSBhZnRlciB3aGljaCBzdGFsYWN0aXRlcyBhbmQgc3RhbGFnbWl0ZXMgYWx0ZXJuYXRlLiZuYnNwOzxcL3A+XHJcblxyXG48cD5IZXJlIGlzIGFuIGV4YW1wbGUgY2F2ZSAxNCB1bml0cyBsb25nIGFuZCA1IHVuaXRzIGhpZ2ggKHRoZSBpbWFnZSBjb3JyZXNwb25kcyB0byB0aGUgZXhhbXBsZSk6Jm5ic3A7PFwvcD5cclxuXHJcbjxwIHN0eWxlPVwidGV4dC1hbGlnbjogY2VudGVyO1wiPjxpbWcgYWx0PVwiXCIgc3JjPVwiaHR0cHM6XC9cL3VwbG9hZC5hY21pY3BjLm5ldFwvYzZmZDQ5NmQtY2NmNS00ZjlkLWEwNmUtMzJiMTIxZmM2YTgyXC8tXC9wcmV2aWV3XC9cIiBzdHlsZT1cIndpZHRoOiAyNzFweDsgaGVpZ2h0OiAxMDhweDtcIiBcLz48XC9wPlxyXG5cclxuPHA+VGhlIEphcGFuZXNlIGZpcmVmbHkgaXMgbm90IHRoZSB0eXBlIHRoYXQgd291bGQgZmx5IGFyb3VuZCB0aGUgb2JzdGFjbGUsIGluc3RlYWQgaXQgd2lsbCBjaG9vc2UgYSBzaW5nbGUgaGVpZ2h0IGFuZCByYW0gZnJvbSBvbmUgZW5kIG9mIHRoZSBjYXZlIHRvIHRoZSBvdGhlciBkZXN0cm95aW5nIGFsbCBvYnN0YWNsZXMgaW4gaXRzIHBhdGggd2l0aCBpdHMgbWlnaHR5IGt1bmctZnUgbW92ZXMuJm5ic3A7PFwvcD5cclxuXHJcbjxwPkluIHRoZSBwcmV2aW91cyBleGFtcGxlLCBjaG9vc2luZyB0aGUgNHRoIGxldmVsIGZyb20gdGhlIGdyb3VuZCBoYXMgdGhlIGZpcmVmbHkgZGVzdHJveWluZyBlaWdodCBvYnN0YWNsZXM6Jm5ic3A7PFwvcD5cclxuXHJcbjxwIHN0eWxlPVwidGV4dC1hbGlnbjogY2VudGVyO1wiPjxpbWcgYWx0PVwiXCIgc3JjPVwiaHR0cHM6XC9cL3VwbG9hZC5hY21pY3BjLm5ldFwvYmZjYmI5NGYtMGUxNS00ZmY5LWIyZWYtNDNlMDdjN2VlNTAzXC8tXC9wcmV2aWV3XC9cIiBzdHlsZT1cIndpZHRoOiAyOTJweDsgaGVpZ2h0OiAxMDhweDtcIiBcLz48XC9wPlxyXG5cclxuPHA+VGhpcyBpcyBub3QgdGhlIGJlc3QgY2hvaWNlIGJlY2F1c2UgdGhlIGZpcmVmbHkgd2lsbCBlbmQgdXAgbGVzcyB0aXJlZCBpZiBpdCBjaG9vc2VzIGVpdGhlciBsZXZlbCBvbmUgb3IgZml2ZSwgYXMgdGhhdCB3b3VsZCByZXF1aXJlIGRlc3Ryb3lpbmcgb25seSBzZXZlbiBvYnN0YWNsZXMuJm5ic3A7PFwvcD5cclxuXHJcbjxwPllvdSBhcmUgZ2l2ZW4gdGhlIHdpZHRoIGFuZCBsZW5ndGggb2YgdGhlIGNhdmUgYW5kIHRoZSBzaXplcyBvZiBhbGwgb2JzdGFjbGVzLiZuYnNwOzxcL3A+XHJcblxyXG48cD5Xcml0ZSBhIHByb2dyYW0gdGhhdCBkZXRlcm1pbmVzIHRoZSBtaW5pbXVtIG51bWJlciBvZiBvYnN0YWNsZXMgdGhlIGZpcmVmbHkgbmVlZHMgdG8gZGVzdHJveSB0byByZWFjaCB0aGUgZW5kIG9mIHRoZSBjYXZlLCBhbmQgb24gaG93IG1hbnkgZGlzdGluY3QgbGV2ZWxzIGl0IGNhbiBhY2hpZXZlIHRoYXQgbnVtYmVyLiZuYnNwOzxcL3A+XHJcbiIsImlucHV0IjoiPHA+VGhlIGZpcnN0IGxpbmUgY29udGFpbnMgdHdvIGludGVnZXJzIE4gYW5kIEgsIDIgJmxlOyBOICZsZTsgMjAwMDAwLCAyICZsZTsgSCAmbGU7IDUwMDAwMCwgdGhlIGxlbmd0aCBhbmQgaGVpZ2h0IG9mIHRoZSBjYXZlLiBOIHdpbGwgYWx3YXlzIGJlIGV2ZW4uJm5ic3A7PFwvcD5cclxuXHJcbjxwPlRoZSBuZXh0IE4gbGluZXMgY29udGFpbiB0aGUgc2l6ZXMgb2YgdGhlIG9ic3RhY2xlcywgb25lIHBlciBsaW5lLiBBbGwgc2l6ZXMgYXJlIHBvc2l0aXZlIGludGVnZXJzIGxlc3MgdGhhbiBILiZuYnNwOzxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPk91dHB1dCB0d28gaW50ZWdlcnMgc2VwYXJhdGVkIGJ5IGEgc2luZ2xlIHNwYWNlIG9uIGEgc2luZ2xlIGxpbmUuIFRoZSBmaXJzdCBudW1iZXIgaXMgdGhlIG1pbmltdW0gbnVtYmVyIG9mIG9ic3RhY2xlcyB0aGUgZmlyZWZseSBoYXMgdG8gZGVzdHJveSBhbmQgdGhlIHNlY29uZCBpcyB0aGUgbnVtYmVyIG9mIGxldmVscyBvbiB3aGljaCB0aGF0IGNhbiBiZSBhY2hpZXZlZC4mbmJzcDs8XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIxIiwiaHRtbF90aXRsZSI6IjAiLCJwcm9ibGVtX2xhbmdfdGNvZGUiOiJFbmdsaXNoIn1d