Сонне стадо корів (срібло)#10344
корів фермера Джона постійно забрідають у віддалені куточки ферми! Йому потрібна твоя допомога, щоб зібрати їх разом.
Основне поле на фермі довге і вузьке, його можна уявити як числову лінію, де корова може займати будь-яке ціле число. корів наразі знаходяться в різних цілочисельних координатах, і фермер Джон хоче перемістити їх так, щоб вони займали послідовні місця (наприклад, позиції , , , , і ).
На жаль, корови досить сонні, і фермеру Джону важко привернути їхню увагу, щоб змусити рухатися. У будь-який момент часу він може змусити корову рухатися, тільки якщо вона є "точкою кінця" (мінімальною або максимальною позицією серед усіх корів). Коли він переміщує корову, він може проінструктувати її переміститися в будь-яке незайняте цілочисельне місце, якщо в цьому новому місці вона більше не є кінцевою точкою. Зверніть увагу, що з часом ці рухи зближують корів.
Визначте мінімальну та максимальну кількість можливих ходів, перш ніж корови згрупуються в послідовних місцях.
У першому рядку записано число (3 \leq n \leq 10^5). Кожен з наступних рядків містить цілочисельне місцезнаходження окремої корови в діапазоні 1 \ldots 10^9.
У першому рядку вкажіть мінімальну кількість ходів, яку потрібно зробити фермеру Джону для групування корів разом. У другому рядку виведіть максимальну кількість ходів, яку фермер Джон може зробити, перш ніж корови згрупуються разом.
Приклад 1
Мінімальна кількість ходів дорівнює - якщо фермер Джон переміщує корову з позиції в позицію , то корови знаходяться в наступних одна за одною місцях , , . Максимальна кількість ходів дорівнює . Наприклад, корова з позиції переміщується в позицію , потім корова з позиції переміщується в позицію .