Тренер слонів

Обмеження: 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 рази пересувається вправо.

У другому прикладі приклад виконання ходів:

1. коти з номерами 2, 3 пересуваються вправо

2. коти з номерами 2, 3, 4 пересуваються вправо

3. коти з номерами 1, 2, 3, 4 пересуваються вправо

4. кіт з номером 5 пересувається вліво 3 рази

5. коти з номерами 5, 6 пересуваються вліво 3 рази