Задача Подняться на лестницу При прохождении компьютерной игры Вася дошел до финального испытания. Ему необходимо взобраться на вершину пирамиды. Вокруг пирамиды идет лестница, однако за долгие годы некоторые из ступенек этой лестницы стали слишком опасными для того, чтобы можно было на них наступать.

Вася очень аккуратно проходил все предыдущие испытания, и поэтому у него есть все подсказки о том, на какие ступеньки наступать нельзя.

Лестница состоит из N ступенек, пронумерованных от 1 до N от основания пирамиды до её вершины, и в ней K опасных ступенек. Кроме того, персонаж Васи за одну секунду может сделать один шаг и подняться на 1, 2, …S ступенек.

До прохождения испытания персонаж стоит перед первой ступенькой, а для успешного его прохождения требуется оказаться на N-ой ступеньке.

Определите минимальное и максимальное время, за которое Вася может пройти финальное испытание.

Формат входных данных
В первой строке входного файла записаны три целых числа N, K и S (1 ≤ N ≤ 200 000, 1 ≤ S 0, то во второй строке записаны K различных целых чисел ai (1 ≤ ai < N) — номера опасных ступенек. Гарантируется, что можно подняться на вершину пирамиды, не наступая на опасные ступеньки. В 80 % тестов N ≤ 1 000.
Формат выходных данных
В единственной строке выходного файла выведите два целых числа: минимальное и максимальное время, за которое Вася может пройти финальное испытание.

оля2044    1   19.11.2020 21:38    9