题目描述

小蓝有一个圆形糖果转盘。转盘上按顺时针方向放着 $N$ 颗糖果，第 $i$ 颗糖果的颜色用一个小写英文字母 $S_i$ 表示。

小蓝要在两颗相邻糖果之间选择一个切口，将圆形转盘切开并展开成一排。展开后，糖果的排列顺序保持原来的顺时针顺序。切口共有 $N$ 个：可以切在第 $i$ 颗和第 $i + 1$ 颗糖果之间，其中 $1 \le i < N$；也可以切在第 $N$ 颗和第 $1$ 颗糖果之间。

如果展开后的一排糖果中，任意两颗相邻糖果的颜色都不同，则称这个切口是漂亮的。

请你计算漂亮切口的数量。

输入格式

第一行包含一个整数 $N$，表示糖果数量。

第二行包含一个长度为 $N$ 的字符串 $S$，其中第 $i$ 个字符 $S_i$ 表示第 $i$ 颗糖果的颜色。

输出格式

输出一行，包含一个整数，表示漂亮切口的数量。

6
ababab

6

5
aabcd

1

8
aaabbcde

0

提示

【样例说明 1】

圆环上每一对相邻糖果颜色都不同。无论从哪个切口切开，展开后的一排糖果中相邻颜色仍然都不同，因此 6 个切口都是漂亮的。

【样例说明 2】

圆环上只有第 1 颗和第 2 颗糖果颜色相同。只有切在这两颗糖果之间，展开后才不会保留这对相邻同色糖果，因此漂亮切口数量为 1。

【样例说明 3】

圆环上至少有两对相邻糖果颜色相同。一次切开只能断开其中一对相邻关系，因此展开后一定仍存在相邻同色糖果，没有漂亮切口。

【评测用例规模与约定】

对于 $30\%$ 的评测用例，$2 \le N \le 200$。

对于 $60\%$ 的评测用例，$2 \le N \le 5000$。

对于所有评测用例，$2 \le N \le 2 \times 10^5$，且 $S$ 仅由小写英文字母组成。