L. Smash the Trash
time limit per test
2 seconds
memory limit per test
512 megabytes
input
standard input
output
standard output

Vitaly is the mayor of Bertown. He prepares for the new mayor election. As a part of his election campaign, he states that he will make Bertown clean again.

There's not that much time till the election starts, so Vitaly's PR manager Arkady decided to clean only the trash resided in the central street of the city. Namely, there are $$$n$$$ dirty places on the central street, numbered from $$$1$$$ to $$$n$$$ from west to east. Arkady wants to dispose of the trash in the $$$i$$$-th place during the $$$i$$$-th day.

As a true patriot of Bertown and the only person in Vitaly's team who is good in arithmetic, you were asked to calculate the minimal number of people to be involved in the cleaning process. This number is selected once before the process starts and stays the same during all $$$n$$$ days.

After talking to a cleaning expert, you realized that one worker can perform one of three actions during day $$$i$$$:

  • dispose of $$$1$$$ kilogram of trash in the place $$$i$$$;
  • move exactly $$$2$$$ kilograms of trash from the place $$$i$$$ to the place $$$i + 1$$$ (of course, this is impossible if $$$i = n$$$);
  • do nothing.

The street is considered clean if there's no trash in all places at the end of the $$$n$$$-th day. Thus, Arkady has to hire multiple people, so that they can work simultaneously to clean the street.

Help Arkady to calculate the minimal number of people to be involved in the cleaning process.

Input

The first line contains one integer $$$n$$$ ($$$1 \le n \le 2 \cdot 10^5$$$) — the number of dirty places in the central street.

The second line contains $$$n$$$ integers $$$t_1, t_2, \dots, t_n$$$ ($$$0 \le t_i \le 2 \cdot 10^5$$$) — the amount of trash in the $$$i$$$-th place, measured in kilograms.

Output

Print one integer — the minimal number of people to be involved in the cleaning process.

Examples
Input
3
5 1 2
Output
4
Input
4
8 1 2 7
Output
7
Note

In the first example, Arkady can clean the street by hiring 4 people:

  • During the first day, 3 kilograms of trash should be disposed of by 3 people, while 2 kilograms of trash should be moved to the next dirty place by one person.
  • During the second day, you have to deal with 3 kilograms of trash in the place 2 using 4 people. It can be easily done if three people dispose of the trash, and one person does nothing.
  • During the third day, 4 workers need to dispose of 2 kilograms of trash.

The same thing can't be done by hiring 3 people since otherwise you'll have to move 4 kilograms of trash from place 1, then move 4 kilograms again from place 2 and then face the situation with 6 kilograms of trash in the third and last place, and 3 people cannot dispose of all 6 kilograms.

In the second example, the answer can't be less than 7, since there are 7 kilograms of trash in the last place, and Arkady has to hire at least 7 people to dispose of it.