### 问题描述 在一个神奇的游戏世界中，小蓝正在探索一片神秘的森林。这片森林充满了各种奇特的怪物和宝藏。小蓝需要解决一个难题来获得宝藏的线索。 给定一个字符串 $s$，它是由小写字母组成的，代表了小蓝在森林中遇到的一系列怪物。小蓝发现，如果在字符串的某个子区间内存在一个字符，它出现的次数不少于该区间长度的一半，那么这个区间是安全的。小蓝想知道，在字符串的所有区间 $[1,x]$ 中（$x \le n$），有多少个安全的区间。 为了解决这个谜题，小蓝需要你的帮助。你能帮他计算出安全区间的数量吗？ ### 输入格式 第一行输入一个整数 $n$（$1 \le n \le 10^5$），表示字符串的长度。 第二行输入一个长度为 $n$ 的只包含小写字符的字符串 $s$，表示小蓝在森林中遇到的怪物序列。 ### 输出格式 输出一个整数，表示在所有区间 $[1,x]$ 中（$x \le n$），有多少个安全的区间。 ### 样例输入 ``` 5 abacc ``` ### 样例输出 ``` 4 ```