34307번 - Purchasing Perishables 다국어

문제

It's the beginning of a new semester at Mines, and Katie is planning out her grocery shopping for the foreseeable future. For each of the next $N$ days she needs ingredients for one meal. To inform her planning, she has compiled a list of prices the store is charging for a meal for each of the next $N$ days she wishes to plan out.

To keep her schedule orderly, Katie has decided to only go shopping on regular intervals. If there is a gap between shopping trips, she will buy exactly enough meals to last until her next purchase or until she has purchased all $N$ meals. For instance, if she is planning out 4ドル$ days and decides on an interval of 3ドル$ days, then she will purchase 3ドル$ meals on the first day, and 1ドル$ meal on the fourth day for a total of 4ドル$ meals.

Katie has a lot of work to do for her Data Structures class and doesn't have time to figure out an optimal interval between shopping trips to minimize her shopping budget. Given the prices for the next $N$ days, help Katie determine the optimal interval and the minimum budget she needs to allocate to purchasing meals for the next $N$ days, given she will only purchase food on regular intervals.

입력

The first line of input contains a single integer 1ドル \leq N \leq 10^5,ドル the number of days for which Katie has prices. The next line contains $N$ space-separated integers $p_1, p_2, \ldots, p_N$ (1ドル \leq p_i \leq 10^9$), where $p_i$ is the price of a meal on the $i^{\text{th}}$ day.

출력

The output should consist of a single integer, the minimum budget required to purchase $N$ meals for the next $N$ days.

제한

힌트