We all know that the winter that has begun will end soon, and everyone will eat pancakes during the Maslenitsa celebration. This will be our task.
N guests are seated at a table, and each has a plate of pancakes in front of them. There are ai pancakes on the plate of the i-th guest. Each guest eats one pancake in one minute, so the time when the last person finishes eating pancakes is equal to the largest value of ai.
Suddenly, another person joined them, and now all those present can shift some of their pancakes (including they can shift all their pancakes, or they may not shift a single pancake) to the newly arrived person. Pancakes are shifted simultaneously and instantly.
The guests want to shift the pancakes in such a way that after shifting they will eat all the pancakes in the minimum time (which is equal to the largest number of pancakes on the guests' plates, including the new guest). Determine the shortest time in which guests can eat their pancakes after being moved.
The program receives as input a natural number N, not exceeding 100.000, – initial number of guests. The next N lines contain natural numbers a
i – the number of pancakes on the plate of the i-th person. The values a
i are given in non-decreasing order, i.e. a
i ≤ a
i+1. The sum of the values of all a
i does not exceed 2·10
9.
The program should output a single integer – the minimum time for all guests to finish eating their pancakes after transferring some of the pancakes to the new guest's plate.
Examples
| # |
Input |
Output |
Explanation |
| 1 |
4
1
3
5
6 |
4 |
4 people are sitting at the table, they have 1, 3, 5, 6 pancakes on their plates. The last guest will give 2 pancakes to the new guest, and the penultimate – 1 pancake, and then everyone, including the new guest, will have no more than 4 pancakes. |