Поликарп получил в подарок массив целых чисел \(a[1 \dots n]\). Он хочет произвести некоторое количество операций (возможно, ноль), чтобы все элементы массива стали одинаковыми (то есть, чтобы стало \(a_1=a_2=\dots=a_n\)).
- За одну операцию он может взять какие-то индексы в массиве и увеличить числа под этими индексами на \(1\).
Например, пусть \(a=[4,2,1,6,2]\). Он может произвести следующую операцию: выбрать индексы 1, 2 и 4 и увеличить их всех на \(1\). В итоге за одну операцию он может получить новое состояние массива \(a=[5,3,1,7,2]\).
За какое минимальное количество операций он может сделать так, что все элементы массива стали равны между собой (то есть, чтобы стало \(a_1=a_2=\dots=a_n\))?
Выходные данные
Для каждого набора входных данных выведите одно целое число — минимальное необходимое количество операций, чтобы сделать все элементы массива \(a\) одинаковыми.
Примечание
Первый набор входных данных:
- \(a=[3,4,2,4,1,2]\) берём \(a_3, a_5\) и проводим на них операцию плюс один, в итоге получаем \(a=[3,4,3,4,2,2]\).
- \(a=[3,4,3,4,2,2]\) берём \(a_1, a_5, a_6\) и проводим на них операцию плюс один, в итоге получаем \(a=[4,4,3,4,3,3]\).
- \(a=[4,4,3,4,3,3]\) берём \(a_3, a_5, a_6\) и проводим на них операцию плюс один, в итоге получаем \(a=[4,4,4,4,4,4]\).
Существуют и другие последовательности из \(3\) операций, после применения которых все элементы станут равны.
Второй набор входных данных:
- \(a=[1000,1002,998]\) 2 раза берём \(a_1, a_3\) и проводим на них операцию плюс один, в итоге получаем \(a=[1002,1002,1000]\).
- \(a=[1002,1002,1000]\) также 2 раза берём \(a_3\) и проводим на нём операцию плюс один, в итоге получаем \(a=[1002,1002,1002]\).
Третий набор входных данных:
- \(a=[12,11]\) берём \(a_2\) и проводим на нём операцию плюс один, в итоге получаем \(a=[12,12]\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
3
6
3 4 2 4 1 2
3
1000 1002 998
2
12 11
|
3
4
1
|