分数: 600 点
问题陈述
Snuke 站在数轴上。他有 L 个耳朵,并且他将按照以下条件沿着数轴连续行走:
- 他从不访问坐标小于 0的点,或者坐标大于 L.
- 的点。 他从一个整数坐标点开始行走,也在一个整数坐标点结束行走。
- 他只在坐标为整数的点上改变方向。
每当Snuke经过一个坐标为整数的点时, i-0.5,其中 i 他就在他的 i号耳朵里放一块石头。
当Snuke走完后,Ringo将以某种顺序重复以下操作,以便对于每个 i,Snuke的 i号耳朵中含有 A_i 块石头:
- 在Snuke的一只耳朵里放一块石头。
- 从Snuke的一只耳朵里取出一块石头。
当Ringo可以自由决定Snuke如何行走时,找到所需的最少操作次数。
约束
- 1 \leq L \leq 2\times 10^5
- 0 \leq A_i \leq 10^9(1\leq i\leq L)
- 输入中的所有值都是整数。
输入
输入由标准输入按以下格式给出:
L A_1 : A_L
输出
打印当Ringo可以自由决定Snuke如何行走时所需的最少操作次数。
示例输入 1
4 1 0 2 3
示例输出 1
1
假设Snuke的行走方式如下:
- 他从坐标开始行走 3 并在坐标结束行走 4,经过坐标 3,4,3,2,3,4 按此顺序。
然后,Snuke 的四只耳朵里将分别装有 0,0,2,3 石头。 Ringo 可以通过在第一个耳朵里放一颗石头来满足要求。
示例输入 2
8 2 0 0 2 1 3 4 1
示例输出 2
3
示例输入 3
7 314159265 358979323 846264338 327950288 419716939 937510582 0
示例输出 3
1