\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 Вивести одне число - мінімальну довжину фрагмента траси, обслуговування якого слід доручити одній фірмі.