给定一个长度为$n$的字符串，求有多少个长度为 3 的子序列满足形如 ABA 的格式，即子序列中的第一个字母等于第三个字母，但它们都不等于第二个字母。 由不同位置的相同字符构成的子序列被认为是不同的子序列，见样例解释。 一个序列被称为字符串 的子序列，当且仅当该序列能仅通过 删除一部分字符得到。

$1\leq n \leq 10^6$

求思路，玄关