시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 3317 1205 888 39.033%

문제

개똥벌레 한 마리가 장애물(석순과 종유석)로 가득찬 동굴에 들어갔다. 동굴의 길이는 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+XHViM2Q5XHVhZDc0XHVjNzU4IFx1ZDA2Y1x1YWUzMFx1YzY0MCBcdWIxOTJcdWM3NzQsIFx1YmFhOFx1YjRlMCBcdWM3YTVcdWM1NjBcdWJiM2NcdWM3NTggXHVkMDZjXHVhZTMwXHVhYzAwIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gXHVjNzc0XHViNTRjLCBcdWFjMWNcdWI2MjVcdWJjOGNcdWI4MDhcdWFjMDAgXHVkMzBjXHVhZDM0XHVkNTc0XHVjNTdjXHVkNTU4XHViMjk0IFx1YzdhNVx1YzU2MFx1YmIzY1x1Yzc1OCBcdWNkNWNcdWMxOWZcdWFjMTJcdWFjZmMgXHVhZGY4XHViN2VjXHVkNTVjIFx1YWQ2Y1x1YWMwNFx1Yzc3NCBcdWNkMWQgXHViYTg3IFx1YWMxYyBcdWM3ODhcdWIyOTRcdWM5YzAgXHVhZDZjXHVkNTU4XHViMjk0IFx1ZDUwNFx1Yjg1Y1x1YWRmOFx1YjdhOFx1Yzc0NCBcdWM3OTFcdWMxMzFcdWQ1NThcdWMyZGNcdWM2MjQuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5cdWNjYWJcdWM5ZjggXHVjOTA0XHVjNWQwIE5cdWFjZmMgSFx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIE5cdWM3NDAgXHVkNTZkXHVjMGMxIFx1YzlkZFx1YzIxOFx1Yzc3NFx1YjJlNC4gKDIgJmxlOyBOICZsZTsgMjAwLDAwMCwgMiAmbGU7IEggJmxlOyA1MDAsMDAwKTxcL3A+XHJcblxyXG48cD5cdWIyZTRcdWM3NGMgTlx1YWMxYyBcdWM5MDRcdWM1ZDBcdWIyOTQgXHVjN2E1XHVjNTYwXHViYjNjXHVjNzU4IFx1ZDA2Y1x1YWUzMFx1YWMwMCBcdWMyMWNcdWMxMWNcdWIzMDBcdWI4NWMgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiBcdWM3YTVcdWM1NjBcdWJiM2NcdWM3NTggXHVkMDZjXHVhZTMwXHViMjk0IEhcdWJjZjRcdWIyZTQgXHVjNzkxXHVjNzQwIFx1YzU5MVx1YzIxOFx1Yzc3NFx1YjJlNC48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5cdWNjYWJcdWM5ZjggXHVjOTA0XHVjNWQwIFx1YWMxY1x1YjYyNVx1YmM4Y1x1YjgwOFx1YWMwMCBcdWQzMGNcdWFkMzRcdWQ1NzRcdWM1N2MgXHVkNTU4XHViMjk0IFx1YzdhNVx1YzU2MFx1YmIzY1x1Yzc1OCBcdWNkNWNcdWMxOWZcdWFjMTJcdWFjZmMgXHVhZGY4XHViN2VjXHVkNTVjIFx1YWQ2Y1x1YWMwNFx1Yzc1OCBcdWMyMThcdWI5N2MgXHVhY2Y1XHViYzMxXHVjNzNjXHViODVjIFx1YWQ2Y1x1YmQ4NFx1ZDU1OFx1YzVlYyBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMCIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVkNTVjXHVhZDZkXHVjNWI0In0seyJwcm9ibGVtX2lkIjoiMzAyMCIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6IkZJUkVGTFkiLCJkZXNjcmlwdGlvbiI6IjxwPkEgSmFwYW5lc2UgZmlyZWZseSBoYXMgZmxvd24gaW50byBhIGNhdmUgZnVsbCBvZiBvYnN0YWNsZXM6IHN0YWxhZ21pdGVzIChyaXNpbmcgZnJvbSB0aGUgZmxvb3IpIGFuZCBzdGFsYWN0aXRlcyAoaGFuZ2luZyBmcm9tIHRoZSBjZWlsaW5nKS4gVGhlIGNhdmUgaXMgTiB1bml0cyBsb25nICh3aGVyZSBOIGlzIGV2ZW4pIGFuZCBIIHVuaXRzIGhpZ2guIFRoZSBmaXJzdCBvYnN0YWNsZSBpcyBhIHN0YWxhZ21pdGUgYWZ0ZXIgd2hpY2ggc3RhbGFjdGl0ZXMgYW5kIHN0YWxhZ21pdGVzIGFsdGVybmF0ZS4mbmJzcDs8XC9wPlxyXG5cclxuPHA+SGVyZSBpcyBhbiBleGFtcGxlIGNhdmUgMTQgdW5pdHMgbG9uZyBhbmQgNSB1bml0cyBoaWdoICh0aGUgaW1hZ2UgY29ycmVzcG9uZHMgdG8gdGhlIGV4YW1wbGUpOiZuYnNwOzxcL3A+XHJcblxyXG48cD48aW1nIGFsdD1cIlwiIHNyYz1cIlwvdXBsb2FkXC9pbWFnZXNcL2ZpcmVmMS5wbmdcIiBzdHlsZT1cImhlaWdodDoxMThweDsgd2lkdGg6MjkwcHhcIiBcLz48XC9wPlxyXG5cclxuPHA+VGhlIEphcGFuZXNlIGZpcmVmbHkgaXMgbm90IHRoZSB0eXBlIHRoYXQgd291bGQgZmx5IGFyb3VuZCB0aGUgb2JzdGFjbGUsIGluc3RlYWQgaXQgd2lsbCBjaG9vc2UgYSBzaW5nbGUgaGVpZ2h0IGFuZCByYW0gZnJvbSBvbmUgZW5kIG9mIHRoZSBjYXZlIHRvIHRoZSBvdGhlciBkZXN0cm95aW5nIGFsbCBvYnN0YWNsZXMgaW4gaXRzIHBhdGggd2l0aCBpdHMgbWlnaHR5IGt1bmctZnUgbW92ZXMuJm5ic3A7PFwvcD5cclxuXHJcbjxwPkluIHRoZSBwcmV2aW91cyBleGFtcGxlLCBjaG9vc2luZyB0aGUgNHRoIGxldmVsIGZyb20gdGhlIGdyb3VuZCBoYXMgdGhlIGZpcmVmbHkgZGVzdHJveWluZyBlaWdodCBvYnN0YWNsZXM6Jm5ic3A7PFwvcD5cclxuXHJcbjxwPjxpbWcgYWx0PVwiXCIgc3JjPVwiXC91cGxvYWRcL2ltYWdlc1wvZmlyZWYyLnBuZ1wiIHN0eWxlPVwiaGVpZ2h0OjEyMnB4OyB3aWR0aDozMDFweFwiIFwvPjxcL3A+XHJcblxyXG48cD5UaGlzIGlzIG5vdCB0aGUgYmVzdCBjaG9pY2UgYmVjYXVzZSB0aGUgZmlyZWZseSB3aWxsIGVuZCB1cCBsZXNzIHRpcmVkIGlmIGl0IGNob29zZXMgZWl0aGVyIGxldmVsIG9uZSBvciBmaXZlLCBhcyB0aGF0IHdvdWxkIHJlcXVpcmUgZGVzdHJveWluZyBvbmx5IHNldmVuIG9ic3RhY2xlcy4mbmJzcDs8XC9wPlxyXG5cclxuPHA+WW91IGFyZSBnaXZlbiB0aGUgd2lkdGggYW5kIGxlbmd0aCBvZiB0aGUgY2F2ZSBhbmQgdGhlIHNpemVzIG9mIGFsbCBvYnN0YWNsZXMuJm5ic3A7PFwvcD5cclxuXHJcbjxwPldyaXRlIGEgcHJvZ3JhbSB0aGF0IGRldGVybWluZXMgdGhlIG1pbmltdW0gbnVtYmVyIG9mIG9ic3RhY2xlcyB0aGUgZmlyZWZseSBuZWVkcyB0byBkZXN0cm95IHRvIHJlYWNoIHRoZSBlbmQgb2YgdGhlIGNhdmUsIGFuZCBvbiBob3cgbWFueSBkaXN0aW5jdCBsZXZlbHMgaXQgY2FuIGFjaGlldmUgdGhhdCBudW1iZXIuJm5ic3A7PFwvcD5cclxuIiwiaW5wdXQiOiI8cD5UaGUgZmlyc3QgbGluZSBjb250YWlucyB0d28gaW50ZWdlcnMgTiBhbmQgSCwgMiAmbGU7IE4gJmxlOyAyMDAwMDAsIDIgJmxlOyBIICZsZTsgNTAwMDAwLCB0aGUgbGVuZ3RoIGFuZCBoZWlnaHQgb2YgdGhlIGNhdmUuIE4gd2lsbCBhbHdheXMgYmUgZXZlbi4mbmJzcDs8XC9wPlxyXG5cclxuPHA+VGhlIG5leHQgTiBsaW5lcyBjb250YWluIHRoZSBzaXplcyBvZiB0aGUgb2JzdGFjbGVzLCBvbmUgcGVyIGxpbmUuIEFsbCBzaXplcyBhcmUgcG9zaXRpdmUgaW50ZWdlcnMgbGVzcyB0aGFuIEguJm5ic3A7PFwvcD5cclxuIiwib3V0cHV0IjoiPHA+T3V0cHV0IHR3byBpbnRlZ2VycyBzZXBhcmF0ZWQgYnkgYSBzaW5nbGUgc3BhY2Ugb24gYSBzaW5nbGUgbGluZS4gVGhlIGZpcnN0IG51bWJlciBpcyB0aGUgbWluaW11bSBudW1iZXIgb2Ygb2JzdGFjbGVzIHRoZSBmaXJlZmx5IGhhcyB0byBkZXN0cm95IGFuZCB0aGUgc2Vjb25kIGlzIHRoZSBudW1iZXIgb2YgbGV2ZWxzIG9uIHdoaWNoIHRoYXQgY2FuIGJlIGFjaGlldmVkLiZuYnNwOzxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjEiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1YzYwMVx1YzViNCJ9XQ==