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.