题目描述

给定一个长度为 $n$ 的仅包含小写字母的字符串 $s$。

你至多可以进行一次如下操作：

• 选取 $s$ 串中的任意一个位置，将其字符修改为任意小写字母。

请计算操作之后的字符串中，满足 $i<j<k$ 且 $s_i,s_j,s_k$ 恰好为字符串 abc 的三元组 $(i,j,k)$ 的最大可能数目。

输入格式

第一行输入一个数 $n$。

第二行输入一个长度为 $n$ 的仅包含小写字母的字符串 $s$

输出格式

输出一个整数，为满足条件的三元组的最大可能数目。

7
aabxbcc

12

10
aaaaabbccc

36

提示

样例 1 解释

将第 $4$ 个字符 x 修改为 b 可以得到 $12$ 个。

数据范围

对于 $100\%$ 的数据，$3\leq n\leq 5\times 10^5$。

• 子任务 1（20 分）：保证 $n\leq 50$。
• 子任务 2（30 分）：保证 $n\leq 5000$。
• 子任务 3（50 分）：无特殊限制。