题目描述

有一个长度为n的字符串$S$，其中字符串中的每个字符是 'A'、'B' 和 'C' 中的一个，你可以对字符串进行一系列的操作，具体操作有：

• 在第奇数次操作（例如：第1次、第3次、...）时，你可以选择字符串中任意一个连续子串“ABC”，并且用“B”替换它（即把三个字符压缩为1个字符）。
• 在第偶数次操作（例如：第2次、第4次、...）时，你可以选择字符串中任意一个连续子串“ABC”，并且用“AC”替换它（即把三个字符压缩为2个字符）。

你最多能够进行多少次操作？

输入

第一行，一个正整数$n$； 第二行，一个长度为$n$的字符串$S$。

输出

输出一行，按照题目要求得到的 $\textit{操作次数}$。

输入样例

6
AABCCC

输出样例

2

数据范围

$1 \le n \le 2\times 10^5$