题目描述

给定一个长度为 $n$ 且仅由字符 a、b、c 构成的字符串 $s$ ，请问其中包含多少个形如 abc 的子串？又包含多少个形如 abc 的子序列？

子串：如果从字符串 $s$ 头部和尾部各自删除若干（可以为 $0$）个字符可以得到字符串 $t$，那么称 $t$ 为 $s$ 的子串。

子序列：如果从字符串 $s$ 中任意删除若干（可以为 $0$）个字符可以得到字符串 $t$，那么称 $t$ 为 $s$ 的子序列。

以字符串 abc 为例，ac 是它的子序列（可以通过直接删除 b 得到），但并不是它的子串（无法从头部或尾部开始，在不删除 a 或 c 的前提下删除 b）。

输入格式

第一行输入一个正整数 $n$.

第二行输入一个字符串 $s$.

输出格式

输出一行两个整数，分别表示形如 abc 的子串与子序列的个数。

5
aabcc

1 4

数据规模与约定

对于 $30\%$ 数据，保证 $1\le n \le 200$.

对于所有数据，保证 $1\le n\le 10^5$.