Roads of Russia
Russia, the largest country in the world, presents a formidable challenge when driving from St. Petersburg to Vladivostok, a journey that spans several days. Given the unpredictability of such a long trip, a state program has been initiated to establish a system of uninterrupted communication along this extensive and intricate route. This program aims not only to ensure communication but also to monitor the road's technical condition, provide urgent medical assistance, and more. To implement this crucial program, contractors must be engaged. It's essential that all companies involved in servicing this route are assigned sections of equal length for maintenance.
The route is dotted with cities and villages, making it practical to allocate work by assigning each company a section from one settlement to another, potentially including other settlements within that section. The distances between these settlements are known. The task is to divide the sequence of distances between settlements such that the sum of distances in each section is equal. The illustration provides an example of how the route can be divided.
To ensure that each company receives a fair and manageable workload, the government seeks to distribute the route so that the sections have the minimum possible length. Your task is to determine this optimal solution.
Input
The input begins with an integer N, representing the number of sections between settlements on the St. Petersburg to Vladivostok route. This is followed by N integers, indicating the distances between settlements. The numbers are separated by spaces and/or line breaks (1 ≤ N ≤ 10000).
Output
Output a single number: the minimum length of a section of the route that should be assigned to one company for maintenance.