Тренер слонів
Обмеження: 2 сек., 256 МіБ
Надивившись, як красиво та синхронно танцюють слони в Таїланді, Андрій вирішив, що він хоче стати дресувальником слонів. «Як повернусь в Україну, обіцяю стати найкращим тренером слонів у світі!» — вигукував Андрій.
На жаль, на вулиці, де живе Андрій слонів немає — є лише коти. Однак Андрій не розгубився — він готовий працювати і з котами.
Для простоти будемо вважати, що вулиця — це пряма лінія, а коти на ній — точки з певними координатами. Всього котів на вулиці є \(n\), \(i\)-й кіт стоїть в точці \(x_i\). Для того, щоб розпочати свою діяльність, Андрію потрібно зібрати всіх котів в одну точку і дати їм тренерські настанови. За одну хвилину Андрій може вибрати довільну множину котів і наказати їм усім одночасно переміститись на одиницю відстані вліво або вправо (всі вибрані коти переміщаються в тому самому напрямку).
Допоможіть Андрію знайти мінімальну кількість хвилин, за яку він зможе зібрати всіх котів в одній точці.
Вхідні дані
У першому рядку задано одне натуральне число \(n\) — кількість котів, що живуть на вулиці Андрія.
У наступному рядку задано \(n\) цілих чисел, розділених пробілами — початкові координати всіх котів.
Вихідні дані
У єдиному рядку виведіть одне ціле число — мінімальну кількість хвилин, за яку Андрій зможе зібрати всіх котів в одній точці.
Обмеження
\(1 \le n \le 10^5\),
\(0 \le x_i \le 10^9\).
Приклади
Вхідні дані (stdin) | Вихідні дані (stdout) |
---|---|
2 4 7 | 3 |
Вхідні дані (stdin) | Вихідні дані (stdout) |
---|---|
7 3 1 1 2 10 7 4 | 9 |
Примітки
У першому прикладі перший кіт 3 рази пересувається вправо.
У другому прикладі приклад виконання ходів:
коти з номерами 2, 3 пересуваються вправо
коти з номерами 2, 3, 4 пересуваються вправо
коти з номерами 1, 2, 3, 4 пересуваються вправо
кіт з номером 5 пересувається вліво 3 рази
коти з номерами 5, 6 пересуваються вліво 3 рази
Надіслати розв'язок
Element Type | Створено | Хто | Задача | Компілятор | Результат | Час (сек.) | Пам'ять (МіБ) | № | Дії |
---|
Element Type | Створено | Хто | Задача | Компілятор | Результат | Час (сек.) | Пам'ять (МіБ) | № | Дії |
---|