B. Лотерея
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Для участия в лотерее пришли $$$n$$$ человек, пронумерованных от $$$1$$$ до $$$n$$$. Каждый получил билет с целым числом от $$$0$$$ до $$$m$$$.

В лотерее равновероятно вытягивается одно целое целевое число от $$$0$$$ до $$$m$$$. Победителями объявляются $$$k$$$ билетов (или меньше, если участников недостаточно) с числами, наиболее близкими к целевому. В случае ничьей победителем объявляется билет, принадлежащий человеку с меньшим номером.

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

Байтек хочет выиграть в лотерею. Таким образом, он хочет узнать, какое число он должен выбрать, чтобы максимизировать шансы на выигрыш. Он хочет узнать наименьшее целое число в случае, если таких целых чисел много. Ваша задача — найти число и рассчитать шансы на выигрыш.

Входные данные

В первой строке входных данных находятся целые числа $$$n$$$, $$$m$$$ и $$$k$$$ ($$$1 \leq n \leq 10^6$$$, $$$0 \leq m \leq 10^{18}$$$, $$$1 \leq k \leq 10^6$$$).

В следующей строке находятся $$$n$$$ целых чисел, обозначающих номера на билетах, полученных людьми, участвующими в лотерее. Эти числа — целые числа в диапазоне от $$$0$$$ до $$$m$$$.

Выходные данные

Вы должны вывести два целых числа. Первое должно быть равно количеству значений целевого числа (от $$$0$$$ до $$$m$$$), при котором Байтек выигрывает, если оптимально выберет свой билет. Второе должно быть равно целому числу, которое Байтек должен выбрать, чтобы максимизировать свой шанс на выигрыш в лотерею.

Примеры
Входные данные
3 6 2
1 4 5
Выходные данные
4 2
Входные данные
7 7 1
2 4 7 3 0 1 6
Выходные данные
1 5
Примечание

В первом примере Байтек выиграет при $$$4$$$-х целевых значениях (а именно $$$0, 1, 2, 3$$$), если выберет целое число $$$2$$$, которое является наименьшим оптимальным значением. Если он выберет $$$3$$$, он также выиграет в четырех случаях, но это значение не является наименьшим.