动态规划

设$dp_{i,j}$为前i个字符相邻字符不相同且第i个字符操作j次的最小次数$\\$ 每一个字符串最多变化26次，在多的话就是浪费操作次数了遍历到i,j的时候去匹配前1个字符的变化的k次情况取最小值即可$\\$ dp方程$\\$

1. i=1 dp[i][j]=min(dp[i][j],dp[i-1][k]+j)$\\$
2. i!=1&&第i个字符操作j次!=第i-1个字符操作k次 dp[i][j]=min(dp[i][j],dp[i-1][k]+j);

题目内容

小红有一个长度为$n$的字符串$S$，现在他可以执行以下的操作：

选择一个索引$i$($1≤i≤n$)，并将$S_i$按照字母表上的顺序、循环右移一位。例如：‘$a$’右移一位为‘$b$’，‘$z$’右移一位为‘$a$’。

小红想知道使得字符串$S$任意两个相邻的字符都不一致的最小操作次数为多少。

输入描述

第一行输入一个整数 $n$($2≤n≤10^5$)代表字符串的长度。

第二行输入一个长度为$n$，且只包含小写字母的字符串$S$。

输出描述

在一行输出$n$个整数，代表使得任意两个相邻的字符都不一致的最小操作次数。

样例1

输入

3
aaa

输出

1

说明

只需要将第二个‘$a$’右移一位即可。

样例2

输入

2
ab

输出

0