核心思路

• 对于第 $k$ 个块，原本两位记为$a, b$。若把该块改成 $[v, v]$，代价是 $\text{cost}_k(v)$=$\mathbf{1}[a\ne v]$+$\mathbf{1}[b\ne v]$=$2$-$\mathbf{1}[a=v]$-$\mathbf{1}[b=v]$ 它只可能是 $0,1,2$ 三种情况： 若 $a=b=v$ 则代价为 $0$；若 $v\in{a,b}$ 且 $a\ne b$ 则代价为 $1$；否则为 $2$。

• 相邻块必须选择不同的 $v$。因此做一维按块推进、按末尾选值的动态规划：

  • 设 $m=\frac{n}{2}$ 为块数，数字候选为 $v\in{0,\dots,9}$。
  • 定义

题目内容

小李在学数学，她头痛欲裂，请你快来帮帮她。

小李面前有 $n$ 个 $1$ 位数字(保证 $n$ 为偶数，数字为 $0-9$ )。她希望每次改变一个数字的值，请你帮她计算，她至少需要修改几个数字的值才能保证这个数列的第 $2i+1$ 和 $2i+2$ 位 $(0<=i<=n/2-1)$ 数字相同，第 $2i$ 和第 $2i+1$ 位 $(1<=i<=n/2-1)$ 数字不同？($1234$ 的第 $1$ 位数字位 $1$ ，第二位数字是 $2$ ，没有第 $0$ 位数字)

输入描述

第一行包括一个正整数 $n$ ，$n$ 不大于 $2e5$ 且为偶数。

第二行包括连续的 $n$ 位数字，为 $0-9$ 。

输出描述

输出一个整数，表示小李最少需要修改几个数字才能满足要求。

样例1

输入

8
11233298

输出

3

说明

其中一种可行的方法为，修改成 $11223399$，需要修改 $3$ 次，可以证明没有更少的次数满足条件。