410514: GYM104031 D Экскаватор

Осень — это время для ремонта тепловых сетей. Конечно, их уже ремонтировали летом, но после испытаний на $$$n$$$ участках теплотрассы случились прорывы. Для каждого прорыва $$$\#j$$$ известен день $$$d_j$$$, в который произошёл прорыв. Данные о прорывах упорядочены хронологически.

Чтобы провести ремонт, нужно сначала выкопать котлован. Тогда рабочие получат доступ к трубам и смогут остановить утечку. Однако есть проблема: для рытья котлована необходим экскаватор, и он имеется в распоряжении ремонтной службы — но только один.

Поэтому ремонтные службы действуют следующим образом.

Когда случается прорыв, оформляется заявка на ремонт участка. Заявки упорядочиваются хронологически; если в один день поступает более одной заявки, они упорядочиваются по номерам. По заявке на участок направляется экскаватор, которому требуется $$$k$$$ полных дней на рытьё котлована. Как только котлован будет вырыт, утечка воды будет остановлена.

В день, когда произошёл первый прорыв, экскаватор был свободен и сразу же был отправлен на рытьё котлована согласно первой поступившей заявке. Завершив работу на одном участке, экскаватор может приступить к работе на другом участке уже на следующий день. Разумеется, если имеется заявка с этого другого участка.

Каждый день Кеше приходится идти вдоль этой самой теплотрассы. Когда утечка остановлена, за ночь над котлованом сооружают мостки, и, начиная со следующего дня после завершения рытья котлована, Кеша может идти по мосткам. Но когда прорыв уже случился, а котлован ещё не выкопан, Кеше приходится обходить этот участок.

Ваша задача — определить максимальное количество участков, которые пришлось обходить Кеше в течение одного дня, а также количество дней, в которые Кеше пришлось обходить максимальное количество участков.

В первой строке содержатся целые числа $$$n$$$ и $$$k$$$ $$$(1 \le n \le 3 \cdot 10^5, \, 1 \le k \le 10^9)$$$ — количество прорывов на теплотрассе и количество дней, необходимое для рытья котлована.

Во второй строке содержится $$$n$$$ целых чисел $$$d_1, d_2, \ldots, d_n$$$ $$$(1 \le d_1 \le d_2 \le ... \le d_n \le 10^9)$$$ — дни, в которые случился очередной прорыв.

Выведите два целых числа: максимальное количество участков, которые пришлось обходить Кеше в течение одного дня, и количество дней, в которые Кеше пришлось обходить максимальное количество участков.

В первых семи подзадачах применяется потестовая система оценки. В графе «Баллы» указано количество баллов за тест и в скобках максимальное количество баллов, которое можно набрать за подзадачу. Участнику сообщаются номера тестов.

Баллы за восьмую подзадачу начисляются только в случае прохождения всех тестов этой подзадачи. Участнику сообщается либо номер первого непройденного теста и результат проверки на этом тесте, либо что все тесты подзадачи пройдены

Для всех подзадач, кроме первой, требуется, чтобы программа верно решала одну или несколько из предшествующих подзадач. Более подробно разбиение на подзадачи показано в таблице ниже.

10 11
1 5 8 17 19 28 32 45 51 64

5
10

Поясним приведённый пример.

В день $$$\#1$$$ на одном из участков теплотрассы случается прорыв. В этот же день туда отправляется экскаватор, который проработает там до дня $$$\#11$$$ включительно. В течение всех этих дней Кеше придётся обходить этот участок.

Пока экскаватор копает котлован на первом участке, произойдут прорывы в дни $$$\#5$$$ и $$$\#8$$$. Заявки на ремонт будут ожидать своего исполнения, а Кеше придётся идти в обход: сначала двух, а потом и трёх участков.

Начиная с дня $$$\#12$$$ над первым котлованом будут сооружены мостки, и Кеше не придётся обходить этот участок. Таким образом, количество участков, которые Кеше приходится обходить в течение дня, уменьшится до $$$2$$$. Экскаватор же отправится на рытьё котлована на втором участке (на котором произошёл прорыв в день $$$\#5$$$. На этом участке экскаватор будет работать до дня $$$\#22$$$ включительно.

Однако в день $$$\#17$$$, а затем в день $$$\#19$$$ произойдут прорывы на четвёртом и пятом участках. Это приведёт к возрастанию количества участков, которые Кеша обходит, сначала до $$$3$$$, а затем до $$$4$$$. Уменьшение количества таких участков до $$$3$$$ произойдёт в день $$$\#23$$$, когда экскаватор, завершив работы на втором участке, приедет работать на третий участок (прорыв на котором произошел в день $$$\#8$$$).

Очередной котлован экскаватор будет копать до дня $$$\#33$$$. Но в дни $$$\#28$$$ и $$$\#32$$$ произойдут прорывы на шестом и седьмом участках. Таким образом, в день $$$\#32$$$ количество участков, которые Кеша обходит, впервые станет равным $$$5$$$.

Впрочем, в день $$$\#33$$$ экскаватор завершит работу на третьем участке, и в день $$$\#34$$$ над этим котлованом уже будут проложены мостки, а экскаватор отправится копать четвёртый котлован. Но в дни $$$\#32$$$ и $$$\#33$$$ Кеша будет вынужден обходить пять участков.

Рытьём четвёртого котлована экскаватор будет занят вплоть до конца дня $$$\#44$$$. В день $$$\#45$$$ над четвёртым участком будут положены мостки, экскаватор начнёт работы на пятом участке, но в этот же день случится прорыв на восьмом участке. Так что Кеше по прежнему нужно будет идти в обход четырёх участков. А в день $$$\#51$$$ количество участков, которые нужно обходить, вновь возрастёт до $$$5$$$ из-за прорыва на девятом участке.

До дня $$$\#55$$$ включительно, пока экскаватор работает на пятом участке, Кеша будет вновь вынужден обходить пять участков. Он будет делать это в течение пяти дней (с $$$\#51$$$ по $$$\#55$$$). В день $$$\#56$$$ над котлованом на пятом участке появятся мостки, и Кеше не потребуется обходить этот участок. А экскаватор отправится на шестой участок, на котором он будет работать до дня $$$\#66$$$ включительно.

Однако в день $$$\#64$$$ произойдёт ещё один — десятый — прорыв. Это означает, что количество участков, которые Кеше придётся обходить, вновь станет равным $$$5$$$. На этот раз он будет обходить пять участков в течение трёх дней. В день $$$\#67$$$ над шестым участком появятся мостки, и количество участков, которые приходится обходить Кеше, опять уменьшится до $$$4$$$.

Более прорывов не происходило (или нам о них неизвестно), так что количество участков, которые Кеше придётся обходить, уже не увеличится. Как можно видеть, максимальное количество участков, которое Кеше пришлось обходить в течение одного дня, составляет $$$5$$$. А совершать обход максимального количества участков ему пришлось в течение $$$10$$$ дней $$$(2 + 5 + 3 = 10)$$$.