← 返回题目列表

AtCoder · yahoo_procon2019_qual_d

D. 耳朵

中文机器翻译题面 查看原题

分数: 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