题目描述

给出一个仅包含 a,b 的字符串 A。在 A 中间任意位置（包括开头结尾）插入一个字符，最大化 aab 作为子序列（可以不连续）在 A 中出现的次数。

输入格式

第一行一个仅包含 a,b 的字符串 A。

输出格式

输出一个整数，为插入一个字符后，aab 作为子序列在 A 中出现的次数的最大值。

样例

样例输入 1

abababa

样例输出 1

10

样例 1 解释

在第一个字符后插入一个 a，变为 aabababa。

样例输入 2

ababbaababa

样例输出 2

33

样例输入 3

aa

样例输出 3

1

数据范围

设 $n$ 为 A 的长度。

对于 $20\%$ 的数据，$n\leq 10$。

对于 $40\%$ 的数据，$n\leq 1000$。

对于另外 $10\%$ 的数据，A 中只有 a。

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

对于 $100\%$ 的数据， $1\leq n\leq 5.5\times 10^6$。