Поликарпу подарили массив \(a[1 \dots n]\) из \(n\) целых чисел. Он может производить с массивом \(a\) следующую операцию не более \(n\) раз:
- Поликарп выбирает индекс \(i\) и прибавляет в одного на свой выбор из его соседей значение \(a_i\). Более формально, Поликарп прибавляет значение \(a_i\) либо к \(a_{i-1}\), либо к \(a_{i+1}\) (если такого соседа не существует, то и прибавить в него нельзя);
- После прибавления Поликарп удаляет \(i\)-й элемент из массива \(a\) (заметим, что в процессе удаления длина массива \(a\) уменьшается на \(1\)).
Два пункта выше совместно обозначают одну операцию.
Например, если у Поликарпа есть массив \(a = [3, 1, 6, 6, 2]\), то он может произвести с ним следующую последовательность операций:
- Поликарп выбирает \(i = 2\) и прибавляет значение \(a_i\) к \((i-1)\)-у элементу: \(a = [4, 6, 6, 2]\);
- Поликарп выбирает \(i = 1\) и прибавляет значение \(a_i\) к \((i+1)\)-у элементу: \(a = [10, 6, 2]\);
- Поликарп выбирает \(i = 3\) и прибавляет значение \(a_i\) к \((i-1)\)-у элементу: \(a = [10, 8]\);
- Поликарп выбирает \(i = 2\) и прибавляет значение \(a_i\) к \((i-1)\)-у элементу: \(a = [18]\);
Заметьте, что Поликарп мог прекратить производить операции в любой из моментов.
Поликарпу стало интересно, сколько минимум операций ему надо произвести, чтобы все элементы массива \(a\) стали одинаковыми (то есть, он хочет, чтобы все \(a_i\) были равны между собой).
Примечание
В первом наборе входных данных ответ может быть получен следующим образом (один из возможных вариантов):
\([3, 1, 6, 6, 2]\) \(\xrightarrow[]{i=4,~прибавляет~влево}\) \([3, 1, 12, 2]\) \(\xrightarrow[]{i=2,~прибавляет~вправо}\) \([3, 13, 2]\) \(\xrightarrow[]{i=1,~прибавляет~вправо}\) \([16, 2]\) \(\xrightarrow[]{i=2,~прибавляет~влево}\) \([18]\). Все элементы в массиве \([18]\) одинаковые.
Во втором наборе входных данных ответ может быть получен следующим образом (один из возможных вариантов):
\([1, 2, 2, 1]\) \(\xrightarrow[]{i=1,~прибавляет~вправо}\) \([3, 2, 1]\) \(\xrightarrow[]{i=3,~прибавляет~влево}\) \([3, 3]\). Все элементы в массиве \([3, 3]\) одинаковые.
В третьем наборе входных данных Поликарпу не надо производить ни одну операцию, так как массив \([2, 2, 2]\) уже содержит одинаковые элементы.
В четвертом наборе входных данных ответ может быть получен следующим образом (один из возможных вариантов):
\([6, 3, 2, 1]\) \(\xrightarrow[]{i=3,~прибавляет~вправо}\) \([6, 3, 3]\) \(\xrightarrow[]{i=3,~прибавляет~влево}\) \([6, 6]\). Все элементы в массиве \([6, 6]\) одинаковые.