Вам задана последовательность \(a=[a_1,a_2,\dots,a_n]\), состоящая из \(n\) положительных целых чисел.
Назовём её подотрезком группу подряд идущих элементов. Каждый подотрезок характеризуется двумя индексами — индексом своего начала и индексом своего окончания. Обозначим за \(a[l,r]\) подотрезок последовательности \(a\) с началом в \(l\) и концом в \(r\), то есть \(a[l,r]=[a_l, a_{l+1}, \dots, a_r]\).
Например, если \(a=[31,4,15,92,6,5]\), то \(a[2,5]=[4,15,92,6]\), \(a[5,5]=[6]\), \(a[1,6]=[31,4,15,92,6,5]\) — её подотрезки.
Разобьем заданную последовательность \(a\) на подотрезки так, чтобы:
- каждый элемент попал ровно в один подотрезок;
- суммы элементов для всех подотрезков равны.
Например, если \(a\) = [\(55,45,30,30,40,100\)], то такую последовательность можно разбить на три подотрезка: \(a[1,2]=[55,45]\), \(a[3,5]=[30, 30, 40]\), \(a[6,6]=[100]\). Каждый элемент принадлежит ровно одному подотрезку, сумма элементов каждого подотрезка равна \(100\).
Назовём толщиной разбиения длину самого длинного подотрезка. Например, толщина разбиения из примера выше равна \(3\).
Найдите минимальную толщину среди всевозможных разбиений заданной последовательности \(a\) на подотрезки требуемым образом.
Примечание
Разбиение в первом наборе входных данных рассмотрено в условии, можно показать, что оно оптимально.
Во втором наборе входных данных разбить на подотрезки можно только оставив единственный подотрезок. Тогда толщина разбиения равна длине всей последовательности, то есть \(4\).
В третьем наборе входных данных оптимальным будет разбиение \([10, 55], [35, 30], [65]\). Толщина разбиения будет равна \(2\).
В четвёртом наборе возможны следующие разбиения:
- \([4] + [1, 1, 1, 1] + [4]\);
- \([4, 1, 1] + [1, 1, 4]\).