Задан массив целых чисел \(a_1, a_2, \dots, a_n\) (\(0 \le a_i \le 10^9\)). За одну операцию можно выбрать целое число \(x\) (\(0 \le x \le 10^{18}\)) и заменить \(a_i\) на \(\lfloor \frac{a_i + x}{2} \rfloor\) (\(\lfloor y \rfloor\) означает округление \(y\) вниз до ближайшего целого числа) для всех \(i\) от \(1\) до \(n\). Обратите внимание, что каждая операция затрагивает все элементы массива.
Выведите наименьшее количество операций, необходимое, чтобы сделать все элементы массива равными.
Если количество операций меньше или равно \(n\), то выведите выбранный \(x\) для каждой операции. Если есть несколько правильных ответов, то выведите любой из них.
Выходные данные
На каждый набор входных данных выведите наименьшее количество операций, необходимое, чтобы сделать все элементы массива равными.
Если количество операций меньше или равно \(n\), то выведите выбранный \(x\) для каждой операции. Если есть несколько правильных ответов, то выведите любой из них.
Примечание
В первом наборе входных данных все элементы уже равны, поэтому достаточно \(0\) операций. Не важно, выведете ли вы потом пустую строку или нет.
Во втором наборе нельзя сделать меньше \(2\) операций. Ответов несколько, рассмотрим последовательность ответов \([2, 5]\). После применения операции с \(x = 2\) массив станет равен \([\lfloor \frac{4 + 2}{2} \rfloor, \lfloor \frac{6 + 2}{2} \rfloor] = [3, 4]\). После применения операции с \(x = 5\) массив станет равен \([\lfloor \frac{3 + 5}{2} \rfloor, \lfloor \frac{4 + 5}{2} \rfloor] = [4, 4]\). Оба элемента одинаковые, поэтому мы закончили.
В последнем наборе нельзя сделать меньше \(6\) операций. Так как \(6\) больше \(n\), не требуется выводить их. Одна из возможных последовательностей ответов — \([0, 0, 0, 0, 0, 0]\). Мы просто делим второй элемент на \(2\) каждый раз и не изменяем первый элемент.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
4
1
10
2
4 6
6
2 1 2 1 2 1
2
0 32
|
0
2
2 5
1
1
6
|