\includegraphics{https://static.e-olymp.com/content/49/4955c09c80f4b0ec22bca0177057c05bba841537.jpg} Россия - самая большая страна в мире. И чтобы проехать на машине через всю страну от Петербурга до Владивостока, потребуется много дней. В дороге может всякое случиться, поэтому недавно была принята государственная программа создания системы бесперебойной связи вдоль всей этой длинной и сложной трассы. Да и не только связь нужна. Нужно следить за техническим состоянием дороги, обеспечивать при необходимости экстренную медицинскую помощь, и еще многое другое нужно обеспечить! Программа эта - очень нужная и важная, и для ее выполнения необходимо найти фирмы - подрядчики. Причем, необходимо, чтобы все фирмы, которые будут обслуживать эту трассу, получили на обслуживание участки равной длины. \includegraphics{https://static.e-olymp.com/content/82/82605159e5b2b2e3f2ea9d1d7719cbffa96f3da6.jpg} Вдоль всей этой трассы стоят города и села, и, конечно, самое разумное решение для равного распределения работ - каждая фирма получит участок вдоль трассы от одного населенного пункта до другого, причем внутри такого участка могут находиться и другие населенные пункты. Расстояния между населенными пунктами известны. Тогда для решения задачи необходимо найти такое разбиение последовательности расстояний между населенными пунктами, чтобы суммы расстояний между городами для каждого участках совпадали. На рисунке приведен пример такого разбиения трассы. Чтобы каждая фирма получила выполнимый объем работ, правительство хочет так распределить трассу, чтобы полученные участки имели минимальную длину. Ваша задача - найти такое решение. \InputFile Входной файл в первой строке содержит одно целое число \textbf{N} - количество участков между населенными пунктами на трассе Петербург - Владивосток. Далее следуют \textbf{N} целых чисел - расстояния между населенными пунктами. Числа разделены пробелами и/или переводами строки (\textbf{1} ≤ \textbf{N} ≤ \textbf{10000}). \OutputFile Вывести одно число - минимальную длину фрагмента трассы, обслуживание которого следует поручить одной фирме.