AT_joig2021_c イルミネーション 2 (Illumination 2)

JOI 高中的学生葵打算在文化节上在走廊里装饰灯饰。 灯饰由 $N$ 个灯泡按东西方向排成一列组成。每个灯泡从西侧开始依次编号为 $1$ 到 $N$。每个灯泡有开（On）和关（Off）两种状态，初始时所有灯泡都是关的状态。 葵希望灯饰最终呈现的图案由数列 $A_1,\ A_2,\ \ldots,\ A_N$ 表示，当 $A_i = 1$ 时，第 $i$ 个灯泡应为开；当 $A_i = 0$ 时，第 $i$ 个灯泡应为关。葵希望尽可能用最短的时间将灯饰调整为目标图案。 葵可以选择最开始进行如下操作一次，也可以选择不进行： - 从西侧起，将一段连续的灯泡全部打开。即选择一个 $1$ 到 $N$ 之间的整数 $r$，将第 $1, 2, \ldots, r$ 个灯泡全部打开。 进行这次操作所需时间可以忽略不计。 之后，可以任意多次进行如下操作： - 选择一个灯泡，将其状态切换（如果是开则关，如果是关则开）。 每进行一次这样的操作需要 $1$ 分钟。 给定灯泡的数量和目标图案，请编写程序求出葵最少需要多少分钟才能将灯饰调整为目标图案。

输入从标准输入中给出，格式如下： > $N$ $A_1$ $A_2$ $\cdots$ $A_N$

输出一个整数，表示将灯饰调整为目标图案所需的最短时间。

## 限制条件 - $1 \leq N \leq 200\,000$。 - $A_i$ 仅为 $0$ 或 $1$（$1 \leq i \leq N$）。 - 输入的所有值均为整数。 ## 小任务 1.（45 分）$N \leq 2\,000$。 2.（55 分）无额外限制。 ## 评测说明 所有提交将在评测系统上进行评测。 提交的源代码在对应小任务的所有评测输入数据上均输出正确结果时，该小任务判为正确。 每次提交的得分为该提交代码通过的小任务得分之和。 本题的得分为**所有提交中得分的最大值**。 当前得分可在“提交结果”标签页的“我的得分情况”中查看。 ## 样例解释 1 例如，葵可以最开始选择 $r = 3$，将第 $1, 2, 3$ 个灯泡打开。该操作耗时 $0$ 分钟。之后，将第 $1$ 个灯泡从开切换为关，将第 $6$ 个灯泡从关切换为开。每次操作耗时 $1$ 分钟，共需 $2$ 分钟。无法在 $2$ 分钟以内完成目标图案，因此输出 $2$。 ## 样例解释 2 在本输入例中，葵不进行最初的操作。之后，将第 $4$ 个灯泡从关切换为开。该操作耗时 $1$ 分钟，无法在 $1$ 分钟以内完成目标图案，因此输出 $1$。 ## 样例解释 3 在本输入例中，葵可以最开始选择 $r = 4$，将第 $1, 2, 3, 4$ 个灯泡打开，从而直接达到目标图案。该操作耗时 $0$ 分钟，因此输出 $0$。 由 ChatGPT 4.1 翻译