You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

字符串

题目描述

定义：字符串s 为一个c-好串（c 为一个字符）时，必须满足：

1. 当$|s| = 1$ ，$s = c$
2. 当$|s| > 1$, $s$ 的左半部分为全为 $c$，右半部分为一个 (c+1)-好串 或者 $s$ 的右半部分为全为 $c$，左半部分为一个 (c+1)-好串

其中 $|s|$ 代表 字符串 $s$ 的长度。

举个例子：当 $s=“cdbbaaaa"$时，$s$ 是一个 a-好串

现在，给你一个字符串 $s$ ( $|s| = 2^k$ ),问最少替换多少个字符，使其为一个 a-好串。

输入格式

第一行一个正整数 $n$，表示字符串长度。

第二行给定字符串 $s$，保证只有小写字母，且 $|s|=n$。

输出格式

输出一个正整数，表示最少替换字符数。

样例

Input 1

8
bbdcaaaa

Output 1

0

Input 2

8
asdfghjk

Output 2

7

Input 3

8
ceaaaabb

Output 3

4

Constraints