处理百奇

$N$个人排成一行。从左往右第$i$个人最初有$A_i$根百奇，并面向左或右。第1个人的左边和第$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$ ().