Вам дан массив \(a\) из \(n\) целых положительных чисел. За одну операцию вы должны выбрать некоторую пару \((i, j)\) такую, что \(1\leq i < j\leq |a|\) и добавить \(|a_i - a_j|\) к концу \(a\) (то есть увеличить \(n\) на \(1\) и сделать новый элемент \(a_n\) равным \(|a_i - a_j|\)). Ваша задача — минимизировать и вывести минимальный элемент \(a\) после выполнения \(k\) операций.
Выходные данные
Для каждого набора входных данных выведите одно целое число — наименьшее возможное значение минимума массива \(a\) после выполнения \(k\) операций.
Примечание
В первом наборе входных данных после любых \(k=2\) операций минимальное значение \(a\) будет равно \(1\).
Во втором наборе входных данных оптимальная стратегия состоит в том, чтобы сначала выбрать \(i=1, j=2\) и добавить \(|a_1 - a_2| = 3\) к концу \(a\), получив \(a=[7, 4, 15, 12, 3]\). Затем выбрать \(i=3, j=4\) и добавить \(|a_3 - a_4| = 3\) к концу \(a\), получив \(a=[7, 4, 15, 12, 3, 3]\). В последней операции выбрать \(i=5, j=6\) и добавить \(|a_5 - a_6| = 0\) в конец \(a\). Тогда минимальный элемент \(a\) станет равным \(0\).
В третьем наборе входных данных оптимальная стратегия состоит в том, чтобы сначала выбрать \(i=2, j=3\) и добавить \(|a_2 - a_3| = 3\) к концу \(a\). Любая вторая операция все равно не приведет к тому, чтобы минимальное значение \(a\) стало меньше \(3\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
4
5 2
3 9 7 15 1
4 3
7 4 15 12
6 2
42 47 50 54 62 79
2 1
500000000000000000 1000000000000000000
|
1
0
3
500000000000000000
|