빼빼로 처리

$N$명의 사람이 일렬로 서 있다. 왼쪽부터 $i$번째 사람은 처음에 빼빼로 $A_i$개를 가지고 있으며, 왼쪽 또는 오른쪽을 바라보고 있다. 첫 번째 사람의 왼쪽과 $N$번째 사람의 오른쪽에는 쓰레기통이 하나씩 있다.

다음 행동을 반복할 수 있다.

1. 빼빼로를 하나 이상 가지고 있는 사람을 한 명 선택한다.
2. 선택한 사람은 바라보는 방향의 이웃에게 빼빼로 하나를 건넨다. 그 방향에 이웃이 없다면 빼빼로를 쓰레기통에 넣는다.
3. 선택한 사람은 바라보는 방향을 반대로 바꾼다.

쓰레기통에 들어간 빼빼로는 다시 꺼낼 수 없다. 사람을 선택하는 순서는 자유롭게 정할 수 있다. 모든 빼빼로를 버리는 데 필요한 행동 횟수의 최솟값을 구하여라.

입력은 다음과 같은 형식으로 주어진다.

$N$ $A_1\ A_2\ \cdots\ A_N$

첫째 줄에 모든 빼빼로를 버리는 데 필요한 행동 횟수의 최솟값을 출력한다.

• $1 \leq N \leq 200\ 000$.
• $0 \leq A_i \leq 10^8$ ().