D. Energetic Cook
time limit per test
1 second
memory limit per test
512 megabytes
input
standard input
output
standard output

Monocarp the Cook works in a large restaurant. He can cook two types of dishes: soup and dumplings. He likes to cook soup more — he spends one unit of energy to cook a soup serving and two units of energy to cook a dumpling serving. Soup and dumplings have different shelf life times:

  • a soup serving must be consumed either on the same day it is cooked or on the next day;
  • a dumpling serving can be stored for an infinite amount of days, so it can be consumed on any day, starting from the day it is cooked.

The restaurant is open for $$$n$$$ consecutive days. During the $$$i$$$-th day, there will be $$$a_i$$$ visitors in the restaurant. Monocarp should give either a serving of soup or a serving of dumplings to each visitor. Monocarp can serve any dish at his discretion. He can also serve different dish types during the day. The only requirement is that the dish's shelf life must be within allowed limits:

  • if a soup serving is given on day $$$1$$$, it must have been cooked on the same day;
  • if a soup serving is given on day $$$i \gt 1$$$, it must have been cooked on day $$$i - 1$$$ or on day $$$i$$$;
  • if a dumpling serving is given on day $$$i$$$, it may have been cooked on any day between $$$1$$$ and $$$i$$$ inclusive.

Every day Monocarp starts with the same amount of energy $$$E$$$ — that is, he can cook any amount of soup and dumplings as long as the total energy he spends during each day is not greater than $$$E$$$. It is impossible to "conserve" energy — for example, if $$$E = 1$$$, Monocarp cannot choose to do nothing on one day and cook a serving of dumplings on the next day.

Monocarp would like to know the minimum possible amount of energy $$$E$$$ which he needs to have at the beginning of every day (same for each day) that would be enough to feed all visitors if he cooks dishes optimally.

Input

The first line of the input contains one integer $$$n$$$ ($$$1 \le n \le 2 \cdot 10^5$$$) — the number of consecutive days the restaurant is open.

The second line contains $$$n$$$ integers $$$a_1, a_2, \dots, a_n$$$ ($$$0 \le a_i \le 10^9$$$), where $$$a_i$$$ is the number of visitors during the $$$i$$$-th day.

Output

Print one integer — the minimum amount of energy Monocarp needs to be able to cook enough dishes for all visitors.

Examples
Input
4
1 1 9 2
Output
4
Input
5
3 1 0 0 15
Output
5
Input
10
5 0 3 7 3 5 0 10 10 10
Output
6