Задача #6729

Для уменьшения аварий на центральной дороге в городе X дорожная служба решила выровнять ямы. Новая яма будет иметь объем (в литрах), равный значению медианы между объемами её самой и соседних слева и справа ям до ремонта. При этом размеры первой и последней ям решили не менять.

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

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

Входные данные. В первой строке входного файла находится число N – количество ям на дороге (натуральное число, не превышающее 10 000). В следующих N строках находятся значения объемов ям (все числа натуральные, не превышающие 25), каждое в отдельной строке. Запишите в ответе два числа: количество ям с наименьшим объемом и общий объем воды, вылившейся из ям обратно на дорогу.

Пример входного файла:

8

10

12

8

6

20

12

16

10

При таких исходных данных после ремонта объем ям будет выглядеть следующим образом 10, 10, 8, 8, 12, 16, 12, 10. В ответе необходимо указать два числа – 2 и 14.