[R60E]折叠 - 代码源竞赛平台

时空限制

2S/512M

题目描述

apiadu 有一张纸条，他想对这张纸条进行折叠操作。

初始时，纸条的长度为 $n+1$，上面共有 $n$ 条折痕，从左到右编号为 $1 \sim n$。折痕均匀分布在纸条上，具体来说，相邻两条折痕之间的距离为 $1$，第 $1$ 条折痕距离纸条左侧边缘的距离也为 $1$，第 $n$ 条折痕距离纸条右侧边缘的距离也为 $1$，每条折痕要么朝里，要么朝外。

当折叠操作进行到任意时刻时，都可以保证折痕依旧均匀分布在纸条上，假设此时纸条的长度为 $m+1$，上面有 $m$ 条折痕，则折痕的方向可以用一个只包含 $0$ 和 $1$ 的序列 $b_1,b_2,\dots,b_m$ 来表示，对于 $i$（$1 \le i \le m$），如果 $b_i=0$，则第 $i$ 条折痕朝里，否则第 $i$ 条折痕朝外。

apiadu 想把通过折叠操作，把纸条的长度折成 $1$，他可以进行的折叠操作如下：

• 假设现在纸条的长度为 $m+1$，折痕方向的序列为 $b_1,b_2,\dots,b_m$，apiadu 可以选择一个正整数 $x$ 满足 $1 \le x \le m$，并且对于所有 $i$ （$1 \le i \le \min(x-1,m-x)$），满足 $b_{x-i} \ne b_{x+i}$，他会将纸条沿第 $x$ 条折痕折叠，折叠后，纸条会按如下方式变化：
  • 如果 $x-1 \le m-x$，则折叠后纸条长度会变为 $m-x+1$，上面有 $m-x$ 条均匀分布的折痕，纸条的折痕方向序列会变为 $b_{x+1},b_{x+2},\dots,b_m$。特别地，当 $m=1$ 且 $x=1$ 时，折叠后纸条长度变为 $1$，折痕数量变为 $0$。
  • 如果 $x-1 > m-x$，则折叠后纸条长度会变为 $x$，上面有 $x-1$ 条均匀分布的折痕，纸条的折痕方向序列会变为 $1-b_1,1-b_2,\dots,1-b_{x-1}$。

请帮助可爱的 apiadu 求出最少需要进行多少次折叠操作，才能使纸条长度变为 $1$。

格式

输入格式

第一行包含一个整数 $n$，表示初始时纸条长度为 $n+1$，上面有 $n$ 条折痕。

第二行包含 $n$ 个整数 $a_1,a_2,\dots,a_n$，表示初始时的折痕方向序列。

输出格式

输出一行一个整数，表示最少需要进行的操作次数。

样例

样例输入 #1

4
0 1 1 0

样例输出 #1

3

样例解释 #1

以下是一种可行的操作方案：

第 $1$ 次操作：选择 $x=2$，操作后折痕方向序列会变成 $[1,0]$。

第 $2$ 次操作：选择 $x=2$，操作后折痕方向序列会变成 $[0]$。

第 $3$ 次操作：选择 $x=1$，操作后纸条长度变为 $1$，折痕数量为 $0$。

可以证明不存在所需操作次数小于 $3$ 的操作方案。

样例输入 #2

5
0 1 0 1 0

样例输出 #2

5

样例输入 #3

6
0 1 1 0 1 1

样例输出 #3

3

数据规模

注意：你只有通过了子任务的所有测试点，才能获得对应子任务的分数。

子任务编号	分数	$n \le$
$1$	$10$	$8$
$2$	$20$	$30$
$3$	$25$	$50$
$4$	$45$	$100$

对于 $100\%$ 的数据，$1 \le n \le 100$，$0 \le a_i \le 1$。