시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 3134 1134 831 38.941%

문제

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

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

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

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

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

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

입력

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

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

출력

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

예제 입력 1

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

예제 출력 1

7 2
W3sicHJvYmxlbV9pZCI6IjMwMjAiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWFjMWNcdWI2MjVcdWJjOGNcdWI4MDgiLCJkZXNjcmlwdGlvbiI6IjxwPlx1YWMxY1x1YjYyNVx1YmM4Y1x1YjgwOCBcdWQ1NWMgXHViOWM4XHViOWFjXHVhYzAwIFx1YzdhNVx1YzU2MFx1YmIzYyhcdWMxMWRcdWMyMWNcdWFjZmMgXHVjODg1XHVjNzIwXHVjMTFkKVx1Yjg1YyBcdWFjMDBcdWI0ZGRcdWNjMmMgXHViM2Q5XHVhZDc0XHVjNWQwIFx1YjRlNFx1YzViNFx1YWMxNFx1YjJlNC4gXHViM2Q5XHVhZDc0XHVjNzU4IFx1YWUzOFx1Yzc3NFx1YjI5NCBOXHViYmY4XHVkMTMwXHVjNzc0XHVhY2UwLCBcdWIxOTJcdWM3NzRcdWIyOTQgSFx1YmJmOFx1ZDEzMFx1Yzc3NFx1YjJlNC4gKE5cdWM3NDAgXHVjOWRkXHVjMjE4KSBcdWNjYWIgXHViYzg4XHVjOWY4IFx1YzdhNVx1YzU2MFx1YmIzY1x1Yzc0MCBcdWQ1NmRcdWMwYzEgXHVjMTFkXHVjMjFjXHVjNzc0XHVhY2UwLCBcdWFkZjggXHViMmU0XHVjNzRjXHVjNWQwXHViMjk0IFx1Yzg4NVx1YzcyMFx1YzExZFx1YWNmYyBcdWMxMWRcdWMyMWNcdWM3NzQgXHViYzg4XHVhYzA4XHVjNTQ0XHVhYzAwXHViYTc0XHVjMTFjIFx1YjRmMVx1YzdhNVx1ZDU1Y1x1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVjNTQ0XHViNzk4IFx1YWRmOFx1YjliY1x1Yzc0MCBcdWFlMzhcdWM3NzRcdWFjMDAgMTRcdWJiZjhcdWQxMzBcdWM3NzRcdWFjZTAgXHViMTkyXHVjNzc0XHVhYzAwIDVcdWJiZjhcdWQxMzBcdWM3NzggXHViM2Q5XHVhZDc0XHVjNzc0XHViMmU0LiAoXHVjNjA4XHVjODFjIFx1YWRmOFx1YjliYyk8XC9wPlxyXG5cclxuPHA+PGltZyBhbHQ9XCJcIiBzcmM9XCJcL3VwbG9hZFwvaW1hZ2VzXC9maXJlZjEucG5nXCIgc3R5bGU9XCJoZWlnaHQ6MTE4cHg7IHdpZHRoOjI5MHB4XCIgXC8+PFwvcD5cclxuXHJcbjxwPlx1Yzc3NCBcdWFjMWNcdWI2MjVcdWJjOGNcdWI4MDhcdWIyOTQgXHVjN2E1XHVjNTYwXHViYjNjXHVjNzQ0IFx1ZDUzY1x1ZDU1OFx1YzljMCBcdWM1NGFcdWIyOTRcdWIyZTQuIFx1Yzc5MFx1YzJlMFx1Yzc3NCBcdWM5YzBcdWIwOThcdWFjMDggXHVhZDZjXHVhYzA0XHVjNzQ0IFx1YzgxNVx1ZDU1YyBcdWIyZTRcdWM3NGMgXHVjNzdjXHVjOWMxXHVjMTIwXHVjNzNjXHViODVjIFx1YzljMFx1YjA5OFx1YWMwMFx1YmE3NFx1YzExYyBcdWI5Y2NcdWIwOThcdWIyOTQgXHViYWE4XHViNGUwIFx1YzdhNVx1YzU2MFx1YmIzY1x1Yzc0NCBcdWQzMGNcdWFkMzRcdWQ1NWNcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YzcwNFx1Yzc1OCBcdWFkZjhcdWI5YmNcdWM1ZDBcdWMxMWMgNFx1YmM4OFx1YzlmOCBcdWFkNmNcdWFjMDRcdWM3M2NcdWI4NWMgXHVhYzFjXHViNjI1XHViYzhjXHViODA4XHVhYzAwIFx1YjBhMFx1YzU0NFx1YWMwNFx1YjJlNFx1YmE3NCBcdWQzMGNcdWFkMzRcdWQ1NzRcdWM1N2NcdWQ1NThcdWIyOTQgXHVjN2E1XHVjNTYwXHViYjNjXHVjNzU4IFx1YzIxOFx1YjI5NCBcdWNkMWQgXHVjNWVjXHViMzVmXHVhYzFjXHVjNzc0XHViMmU0LiAoNFx1YmM4OFx1YzlmOCBcdWFkNmNcdWFjMDRcdWM3NDAgXHVhZTM4XHVjNzc0XHVhYzAwIDNcdWM3NzggXHVjMTFkXHVjMjFjXHVhY2ZjIFx1YWUzOFx1Yzc3NFx1YWMwMCA0XHVjNzc4IFx1YzExZFx1YzIxY1x1Yzc1OCBcdWM5MTFcdWFjMDRcdWM5YzBcdWM4MTBcdWM3NDQgXHViOWQwXHVkNTVjXHViMmU0KTxcL3A+XHJcblxyXG48cD48aW1nIGFsdD1cIlwiIHNyYz1cIlwvdXBsb2FkXC9pbWFnZXNcL2ZpcmVmMi5wbmdcIiBzdHlsZT1cImhlaWdodDoxMjJweDsgd2lkdGg6MzAxcHhcIiBcLz48XC9wPlxyXG5cclxuPHA+XHVkNTU4XHVjOWMwXHViOWNjLCBcdWNjYWIgXHViYzg4XHVjOWY4IFx1YWQ2Y1x1YWMwNFx1Yzc3NFx1YjA5OCBcdWIyZTRcdWMxMmYgXHViYzg4XHVjOWY4IFx1YWQ2Y1x1YWMwNFx1YzczY1x1Yjg1YyBcdWIwYTBcdWM1NDRcdWFjMDRcdWIyZTRcdWJhNzQgXHVhYzFjXHViNjI1XHViYzhjXHViODA4XHViMjk0IFx1YzdhNVx1YzU2MFx1YmIzYyBcdWM3N2NcdWFjZjFcdWFjMWNcdWI5Y2MgXHVkMzBjXHVhZDM0XHVkNTU4XHViYTc0IFx1YjQxY1x1YjJlNC48XC9wPlxyXG5cclxuPHA+XHViM2Q5XHVhZDc0XHVjNzU4IFx1ZDA2Y1x1YWUzMFx1YzY0MCBcdWIxOTJcdWM3NzQsIFx1YmFhOFx1YjRlMCBcdWM3YTVcdWM1NjBcdWJiM2NcdWM3NTggXHVkMDZjXHVhZTMwXHVhYzAwIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gXHVjNzc0IFx1YjU0YywgXHVhYzFjXHViNjI1XHViYzhjXHViODA4XHVhYzAwIFx1ZDMwY1x1YWQzNFx1ZDU3NFx1YzU3Y1x1ZDU1OFx1YjI5NCBcdWM3YTVcdWM1NjBcdWJiM2NcdWM3NTggXHVjZDVjXHVjMThjXHVhYzEyXHVhY2ZjIFx1YWRmOFx1YjdlY1x1ZDU1YyBcdWFkNmNcdWFjMDRcdWM3NzQgXHVjZDFkIFx1YmE4NyBcdWFjMWMgXHVjNzg4XHViMjk0XHVjOWMwIFx1YWQ2Y1x1ZDU1OFx1YjI5NCBcdWQ1MDRcdWI4NWNcdWFkZjhcdWI3YThcdWM3NDQgXHVjNzkxXHVjMTMxXHVkNTU4XHVjMmRjXHVjNjI0LjxcL3A+XHJcbiIsImlucHV0IjoiPHA+XHVjY2FiXHVjOWY4IFx1YzkwNFx1YzVkMCBOXHVhY2ZjIEhcdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiBOXHVjNzQwIFx1ZDU2ZFx1YzBjMSBcdWM5ZGRcdWMyMThcdWM3NzRcdWIyZTQuICgyICZsZTsgTiAmbGU7IDIwMCwwMDAsIDIgJmxlOyBIICZsZTsgNTAwLDAwMCk8XC9wPlxyXG5cclxuPHA+XHViMmU0XHVjNzRjIE5cdWFjMWMgXHVjOTA0XHVjNWQwXHViMjk0IFx1YzdhNVx1YzU2MFx1YmIzY1x1Yzc1OCBcdWQwNmNcdWFlMzBcdWFjMDAgXHVjMjFjXHVjMTFjXHViMzAwXHViODVjIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gXHVjN2E1XHVjNTYwXHViYjNjXHVjNzU4IFx1ZDA2Y1x1YWUzMFx1YjI5NCBIXHViY2Y0XHViMmU0IFx1Yzc5MVx1Yzc0MCBcdWM1OTFcdWMyMThcdWM3NzRcdWIyZTQuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+XHVjY2FiXHVjOWY4IFx1YzkwNFx1YzVkMCBcdWFjMWNcdWI2MjVcdWJjOGNcdWI4MDhcdWFjMDAgXHVkMzBjXHVhZDM0XHVkNTc0XHVjNTdjIFx1ZDU1OFx1YjI5NCBcdWM3YTVcdWM1NjBcdWJiM2NcdWM3NTggXHVjZDVjXHVjMThjXHVhYzEyXHVhY2ZjIFx1YWRmOFx1YjdlY1x1ZDU1YyBcdWFkNmNcdWFjMDRcdWM3NTggXHVjMjE4XHViOTdjIFx1YWNmNVx1YmMzMVx1YzczY1x1Yjg1YyBcdWFkNmNcdWJkODRcdWQ1NThcdWM1ZWMgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjAiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1ZDU1Y1x1YWQ2ZFx1YzViNCJ9LHsicHJvYmxlbV9pZCI6IjMwMjAiLCJwcm9ibGVtX2xhbmciOiIxIiwidGl0bGUiOiJGSVJFRkxZIiwiZGVzY3JpcHRpb24iOiI8cD5BIEphcGFuZXNlIGZpcmVmbHkgaGFzIGZsb3duIGludG8gYSBjYXZlIGZ1bGwgb2Ygb2JzdGFjbGVzOiBzdGFsYWdtaXRlcyAocmlzaW5nIGZyb20gdGhlIGZsb29yKSBhbmQgc3RhbGFjdGl0ZXMgKGhhbmdpbmcgZnJvbSB0aGUgY2VpbGluZykuIFRoZSBjYXZlIGlzIE4gdW5pdHMgbG9uZyAod2hlcmUgTiBpcyBldmVuKSBhbmQgSCB1bml0cyBoaWdoLiBUaGUgZmlyc3Qgb2JzdGFjbGUgaXMgYSBzdGFsYWdtaXRlIGFmdGVyIHdoaWNoIHN0YWxhY3RpdGVzIGFuZCBzdGFsYWdtaXRlcyBhbHRlcm5hdGUuJm5ic3A7PFwvcD5cclxuXHJcbjxwPkhlcmUgaXMgYW4gZXhhbXBsZSBjYXZlIDE0IHVuaXRzIGxvbmcgYW5kIDUgdW5pdHMgaGlnaCAodGhlIGltYWdlIGNvcnJlc3BvbmRzIHRvIHRoZSBleGFtcGxlKTombmJzcDs8XC9wPlxyXG5cclxuPHA+PGltZyBhbHQ9XCJcIiBzcmM9XCJcL3VwbG9hZFwvaW1hZ2VzXC9maXJlZjEucG5nXCIgc3R5bGU9XCJoZWlnaHQ6MTE4cHg7IHdpZHRoOjI5MHB4XCIgXC8+PFwvcD5cclxuXHJcbjxwPlRoZSBKYXBhbmVzZSBmaXJlZmx5IGlzIG5vdCB0aGUgdHlwZSB0aGF0IHdvdWxkIGZseSBhcm91bmQgdGhlIG9ic3RhY2xlLCBpbnN0ZWFkIGl0IHdpbGwgY2hvb3NlIGEgc2luZ2xlIGhlaWdodCBhbmQgcmFtIGZyb20gb25lIGVuZCBvZiB0aGUgY2F2ZSB0byB0aGUgb3RoZXIgZGVzdHJveWluZyBhbGwgb2JzdGFjbGVzIGluIGl0cyBwYXRoIHdpdGggaXRzIG1pZ2h0eSBrdW5nLWZ1IG1vdmVzLiZuYnNwOzxcL3A+XHJcblxyXG48cD5JbiB0aGUgcHJldmlvdXMgZXhhbXBsZSwgY2hvb3NpbmcgdGhlIDR0aCBsZXZlbCBmcm9tIHRoZSBncm91bmQgaGFzIHRoZSBmaXJlZmx5IGRlc3Ryb3lpbmcgZWlnaHQgb2JzdGFjbGVzOiZuYnNwOzxcL3A+XHJcblxyXG48cD48aW1nIGFsdD1cIlwiIHNyYz1cIlwvdXBsb2FkXC9pbWFnZXNcL2ZpcmVmMi5wbmdcIiBzdHlsZT1cImhlaWdodDoxMjJweDsgd2lkdGg6MzAxcHhcIiBcLz48XC9wPlxyXG5cclxuPHA+VGhpcyBpcyBub3QgdGhlIGJlc3QgY2hvaWNlIGJlY2F1c2UgdGhlIGZpcmVmbHkgd2lsbCBlbmQgdXAgbGVzcyB0aXJlZCBpZiBpdCBjaG9vc2VzIGVpdGhlciBsZXZlbCBvbmUgb3IgZml2ZSwgYXMgdGhhdCB3b3VsZCByZXF1aXJlIGRlc3Ryb3lpbmcgb25seSBzZXZlbiBvYnN0YWNsZXMuJm5ic3A7PFwvcD5cclxuXHJcbjxwPllvdSBhcmUgZ2l2ZW4gdGhlIHdpZHRoIGFuZCBsZW5ndGggb2YgdGhlIGNhdmUgYW5kIHRoZSBzaXplcyBvZiBhbGwgb2JzdGFjbGVzLiZuYnNwOzxcL3A+XHJcblxyXG48cD5Xcml0ZSBhIHByb2dyYW0gdGhhdCBkZXRlcm1pbmVzIHRoZSBtaW5pbXVtIG51bWJlciBvZiBvYnN0YWNsZXMgdGhlIGZpcmVmbHkgbmVlZHMgdG8gZGVzdHJveSB0byByZWFjaCB0aGUgZW5kIG9mIHRoZSBjYXZlLCBhbmQgb24gaG93IG1hbnkgZGlzdGluY3QgbGV2ZWxzIGl0IGNhbiBhY2hpZXZlIHRoYXQgbnVtYmVyLiZuYnNwOzxcL3A+XHJcbiIsImlucHV0IjoiPHA+VGhlIGZpcnN0IGxpbmUgY29udGFpbnMgdHdvIGludGVnZXJzIE4gYW5kIEgsIDIgJmxlOyBOICZsZTsgMjAwMDAwLCAyICZsZTsgSCAmbGU7IDUwMDAwMCwgdGhlIGxlbmd0aCBhbmQgaGVpZ2h0IG9mIHRoZSBjYXZlLiBOIHdpbGwgYWx3YXlzIGJlIGV2ZW4uJm5ic3A7PFwvcD5cclxuXHJcbjxwPlRoZSBuZXh0IE4gbGluZXMgY29udGFpbiB0aGUgc2l6ZXMgb2YgdGhlIG9ic3RhY2xlcywgb25lIHBlciBsaW5lLiBBbGwgc2l6ZXMgYXJlIHBvc2l0aXZlIGludGVnZXJzIGxlc3MgdGhhbiBILiZuYnNwOzxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPk91dHB1dCB0d28gaW50ZWdlcnMgc2VwYXJhdGVkIGJ5IGEgc2luZ2xlIHNwYWNlIG9uIGEgc2luZ2xlIGxpbmUuIFRoZSBmaXJzdCBudW1iZXIgaXMgdGhlIG1pbmltdW0gbnVtYmVyIG9mIG9ic3RhY2xlcyB0aGUgZmlyZWZseSBoYXMgdG8gZGVzdHJveSBhbmQgdGhlIHNlY29uZCBpcyB0aGUgbnVtYmVyIG9mIGxldmVscyBvbiB3aGljaCB0aGF0IGNhbiBiZSBhY2hpZXZlZC4mbmJzcDs8XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIxIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWM2MDFcdWM1YjQifV0=