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:
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:
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.
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.
Print one integer — the minimum amount of energy Monocarp needs to be able to cook enough dishes for all visitors.
41 1 9 2
4
53 1 0 0 15
5
105 0 3 7 3 5 0 10 10 10
6