Олимпиадный тренинг

Задача . Посетить все


Громозека играет в одиночную игру, используя числовую прямую и N фишек. Каждая из фишек расположена в некоторой целочисленной координате. Заметьте, несколько фишек могут быть размещены в одной и той же координате.
Цель игры: посетить фишками все M координат X1, X2, ..., XM, повторив следующий ход.
Ход: выберите фишку с координатой X. Поместите эту фишку в координату X+1 или X-1.
Обратите внимание, что координаты, где мы первоначально размещены фишки, уже считаются посещенными.
Найдите минимальное количество ходов, необходимое для достижения цели.

Входные данные
В первой строке программа получает на вход два целых числа: N и M (1 <= N, M <= 105). Во второй строке записаны M целых чисел X1, X2, ..., XM (-105 <= Xi <= 105). Все числа Xi различны.

Выходные данные
Выведите на экран ответ на задачу.
 
Примеры
Входные данные Выходные данные Пояснение
1 2 5
10 12 1 2 14
5 Цель может быть достигнута за пять ходов следующим образом, и это минимально необходимое количество ходов.
Сначала поместите две фишки в координаты 1 и 10.
Переместите фишку с координатой 1 на 2.
Переместите фишку с координатой 10 на 11.
Переместите фишку с координатами 11 на 12.
Переместите фишку с координатами 12 на 13.
Переместите фишку с координатами 13 на 14.
2 3 7
-10 -3 0 9 -100 2 17
19  
3 100 1
-100000
0  



time 1000 ms
memory 256 Mb
Правила оформления программ и список ошибок при автоматической проверке задач

Статистика успешных решений по компиляторам
 Кол-во
С++ Mingw-w644
Python1
Комментарий учителя