Вам задано \(n\) фишек на числовой прямой. \(i\)-я фишка располагается в целочисленной координате \(x_i\). Некоторые фишки могут иметь одинаковые координаты.
Вы можете совершать любой из следующих двух типов ходов любое (возможно, нулевое) количество раз над любой фишкой:
Заметьте, что разрешается перемещать фишки в любые целочисленные координаты, включая нулевую и отрицательные.
Ваша задача — найти минимальное суммарное количество монет, необходимое для того, чтобы переместить все \(n\) фишек в одну координату (то есть после какой-то последовательности ходов все \(x_i\) должны быть равны).
Первая строка входных данных содержит одно целое число \(n\) (\(1 \le n \le 100\)) — количество фишек.
Вторая строка входных данных содержит \(n\) целых чисел \(x_1, x_2, \dots, x_n\) (\(1 \le x_i \le 10^9\)), где \(x_i\) равно координате \(i\)-й фишки.
Выведите одно целое число — минимальное суммарное количество монет, необходимое для того, чтобы переместить все \(n\) фишек в одну координату.
В первом тестовом примере вам необходимо переместить первую фишку на \(2\) вправо и вторую фишку на \(1\) вправо или переместить третью фишку на \(2\) влево и вторую фишку на \(1\) влево, таким образом ответ равен \(1\).
Во втором тестовом примере вам необходимо передвинуть две фишки с координатами \(3\) на \(1\) влево, таким образом ответ равен \(2\).
5 2 1 2 2 3 3 4 4 5
1 2
5 3 1 2 1 3 1 4 1 5
2 3 4
1 1
0
1000 ms 256 Mb Правила оформления программ и список ошибок при автоматической проверке задач