Description

K理事长正在思考日本信息学奥林匹克竞赛选手的应援道具的logo问题。某天，K理事长突发奇想，想要设计一个用’J’，’O’，’I’三种文字环形排列的logo，意为希望选手能从JOI中收获快乐的意思。
(注：“环形地”在日文中的表述为“円状に”，“円”读作“en”，再加上“JOI”三个字即为“enjoy”……)
如下所示，对于任意非负整数k，我们定义标号为k的JOI序列Sk为：
·S0为’J’，’O’，’I’中任一字符构成的长度为1的字符串
·S[k+1]为最初4^k个字符都是’J’，接下来的4^k个字符都是’O’，接下来的4^k个字符都是’I’，最后4^k个字符是字符串Sk的长为4^(k+1)的字符串
现在，K理事长在纸上写下了由4^K个文字构成的一个环形字符串，字符串中每个字符都是’J’，’O’，’I’中的一个。K理事长想要修改一些文字，使得得到的字符串从某个起点开始顺时针读一圈后可以得到SK。在满足条件的情况下，要求修改的文字数量最少。

Input

第一行一个正整数K，表示K理事长在纸上写下了一个长度为4^K的环状字符串。
第二行一个由’J’，’O’，’I’三个字符构成的长为4^K的字符串，表示纸上的环形字符串从某个起点出发顺时针阅读一圈得到的字符串。

Output

输出一行一个整数，表示修改文字数量的最小值。

Sample Input

2
JJOIJJOJOIOJOOOI

Sample Output

7

题解：

其实这题挺水的，但我一开始看题是，却理解错了题意，然后就没有然后了……
好了，回归正题，这题怎么做呢？其实只要理解了题意，题目自然就变得十分简单了（题目不懂的，找你身边的小伙伴们问一下吧），我们先把读入的“JOI”串再复制一份，这样方便做，然后统计出每个位置上“J”、“O”、“I”分别的个数，统计个数后，就看看下面的东西吧。（我知道我很懒╮(╯▽╰)╭）

---

$$你中奖了！（呵呵）$$

---

$$赠送代码一份……$$

vari,j,k,s,l,r,m,ans,la:longint;a:array[1..2100000] of char;x,y,z:array[0..2100000] of longint;
procedure dg(s,n,m:longint);
varl,r:longint;
beginif m>1 thenbeginl:=s;r:=l+n;ans:=ans+n-x[r]+x[l];l:=r;r:=l+n;ans:=ans+n-y[r]+y[l];l:=r;r:=l+n;ans:=ans+n-z[r]+z[l];dg(r,n div 4,m-3*n);end;
end;
beginassign(input,'logo.in');reset(input);assign(output,'logo.out');rewrite(output);readln(k);s:=1;for i:=1 to k do s:=s*4;for i:=1 to s do read(a[i]);for i:=s+1 to s*2 do a[i]:=a[i-s];s:=s*2;for i:=1 to s dobeginx[i]:=x[i-1];y[i]:=y[i-1];z[i]:=z[i-1];if a[i]='J' then inc(x[i]) elseif a[i]='O' then inc(y[i]) elseif a[i]='I' then inc(z[i]);end;k:=s div 8;la:=maxlongint;for i:=1 to s div 2 dobeginans:=0;m:=s div 2-k*3;l:=i-1;r:=l+k;ans:=ans+k-x[r]+x[l];l:=r;r:=l+k;ans:=ans+k-y[r]+y[l];l:=r;r:=l+k;ans:=ans+k-z[r]+z[l];dg(r,k div 4,m);if ans<la then la:=ans;end;writeln(la);close(input);close(output);
end.