ztm 的羊腿修整

题目描述

ztm 最近从国外订购了一个超极品羊腿！

这个羊腿超级大，质量超级好，但是非常可惜，因为运送路途遥远，它中间有一部分的肉看起来不再那么优秀

于是 ztm 决定修整一下这只羊腿

但是 ztm 并不会专业师傅的 薄切刀法，只会他独创的 迪拜刀法，也就是直接挑两个位置，咔嚓两刀，去头去尾，保留中间部分！(当然 ztm 可以选择只切一刀，不切，或者扔掉整个羊腿)

假设这只羊腿现在被 ztm 看作是从左往右依次 $n$ 个均匀的部分，每个部分的羊腿肉可以用一个符号 $A$ 来表示非常极品，用一个符号 $B$ 来表示不再那么优秀

显然对于 ztm 来说，他切掉的 $A$ 越多，留下的 $B$ 越多，就会越心痛

但是老生常谈的一句话——鱼和熊掌不可兼得

在切的同时一定会同时切掉 $A$ 和 $B$ 类的肉

所以 ztm 最后决定，不同切法的心痛程度=$max($切掉$A$的数量，留下$B$的数量$)$

现在 ztm 想知道对于这只羊腿，他的心痛程度最小是多少？

输入格式

输入第一行包含一个整数 $n$ 表示羊腿长度

接下来一行一个长度为 $n$ 仅由 $A,B$ 组成的字符串，表示这个羊腿从左往右每个部分肉的品质

输出格式

输出 ztm 最小的心痛程度

数据范围

数据点编号

$n$的范围

$1$

$1 \leq n \leq 100$ 且字符串只包含$A$

$2$~$3$

$1 \leq n \leq 10^2$

$4$~$5$

$1 \leq n \leq 2*10^3$

$6$~$10$

$1 \leq n \leq 2*10^6$

样例输入

13
ABBABBABBABBA

样例输出

3