Находясь у Киры дома, Джоске увидел на столе лист с написанной на нем задачей.
Задача звучала так. Есть массив \(a\) длины \(n\). На этом массиве нужно сделать следующее:
- выбрать число \(k > 1\);
- разбить массив на \(k\) подотрезков \(^\dagger\);
- посчитать сумму в каждом из \(k\) подотрезков и записать их в другой массив \(b\) (где сумма подотрезка \((l, r)\) равна \({\sum_{j = l}^{r}a_j}\));
- итоговым счетом такого разбиения будет \(\gcd(b_1, b_2, \ldots, b_k)^\ddagger\).
Задача заключается в поиске такого разбиения, чтобы счет был максимально возможным. Джоске заинтересовался данной задачей, но не силен в информатике. Помогите ему найти максимально возможный счет.
\(^\dagger\) Разбиением массива на \(k\) подотрезков называется \(k\) пар чисел \((l_1, r_1), (l_2, r_2), \ldots, (l_k, r_k)\) таких, что \(l_i \le r_i\) и для каждого \(1 \le j \le k - 1\) верно \(l_{j + 1} = r_j + 1\), а также \(l_1 = 1\) и \(r_k = n\). Эти пары представляют сами подотрезки.
\(^\ddagger\) \(\gcd(b_1, b_2, \ldots, b_k)\) обозначает наибольший общий делитель (НОД) массива \(b\).
Выходные данные
Для каждого набора входных данных выведите единственное число — максимальный счет при оптимальном разбиении.
Примечание
В первом наборе входных данных можно выбрать \(k = 2\) и разбить массив на подотрезки \((1, 2)\) и \((3, 4)\).
Тогда счет такого разбиения будет равен \(\gcd(a_1 + a_2, a_3 + a_4) = \gcd(2 + 2, 1 + 3) = \gcd(4, 4) = 4\).
В четвертом наборе входных данных можно выбрать \(k = 3\) и разбить массив на подотрезки \((1, 2), (3, 5), (6, 6)\).
Счётом разбиения будет \(\gcd(1 + 2, 1 + 1 + 1, 3) = 3\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
6
4
2 2 1 3
2
1 2
3
1 4 5
6
1 2 1 1 1 3
10
12 30 37 88 12 78 89 17 2 12
6
7 7 7 7 7 7
|
4
1
5
3
1
21
|