• محدودیت زمان: ۱ ثانیه
• محدودیت حافظه: ۲۵۶ مگابایت

A bunch of students had booked a train for the SEMANTIC competition. The train consists of several carriages and each carriage has some passengers in it, with a restroom located between each two carriages. There are also restrooms before the first carriage and after the last carriage. After the train stops, suddenly everyone decides to go to the restroom before getting off the train. and long queues have been formed. We know that each person either chooses the restroom on the right or on the left side of their carriage and waits until he/she can go in the restroom. we know each person spends exactly one minute in the restroom. Among all the possible ways that each passenger can choose to stand in one of two adjacent restroom queues, determine the minimum waiting time $t$ for the train that everyone can get off the train after $t$ minutes.

input

the first line consist $n$ the number of train carriages. the next line consist of n numbers. $a_i$ shows the number of passengers in carriage number $i$.

$$1 \le n \le 1000,000$$

$$1 \le a_i \le 1000,000,000$$

output

your output should consist a single number $t$ that shows the minimum waiting time for the train in best case.

example

sample input 1

4
1 2 1 1

sample output 1

1

sample input 2

4
1 2 2 1

sample output 2

2