P12977 泪雨 Namid[A]me

> 涙目 変わらずの雨模様\ 泪眼不变的烟雨迷蒙\ その夢の淵ギリギリで\ 在那梦的深渊倾盆而下\ —— ヒトリエ《Namid[A]me》 最终，只剩我一人了。

给定小写英文字母和 ```?``` 组成的字符串 $s$。 “泪雨”定义为这样的串：这是一个回文串，并且 ```?``` 的个数大于等于小写英文字符的个数。 请对于是“泪雨”的 $s$ 的所有子串，求出它们问号位置的和之和。（位置下标从 $1$ 开始） **形式化题意**：定义： $$ f(l,r)= \sum_{i=l}^{r} [s_i=\texttt{?}]\cdot i \\ g(l,r)=\big[\sum_{i=l}^r{[s_i=\texttt{?}] \geq} \frac{r-l+1}{2}\big]\big[ s[l,r]\text{ is a palindrome} \big] $$ 请你求出 $\sum_{l=1}^{n} \sum_{r=l}^{n} g(l,r)\cdot f(l,r)$，其中 $n=\lvert s\rvert$。

第一行一个正整数 $n$，表示 $s$ 的长度 $n$。 第二行输入仅由小写英文字母和问号组成的字符串 $s$。

一行一个正整数，表示答案。

**样例解释：** 样例 $1$ 中，$[2,2],[3,3],[1,4],[2,3]$ 都是符合要求的回文串，并且所求的问号位置之和为 $2+3+(2+3)+(2+3)=15$。 以下是数据范围。 | Subtask | $n$ | 特殊性质 | 分值 | 子任务依赖 | | :----------: | :----------: | :----------: | :----------: | :----------: | | $1$ | $\leq 500$ | 无 | $10$ | - | | $2$ | $\leq 7000$ | 无 | $15$ | $1$ | | $3$ | $\leq 2\times 10^6$ | $s$ 中仅有 ```?``` | $5$ | - | | $4$ | $\leq 2\times 10^6$ | 字符串随机生成 | $10$ | $1$ | | $5$ | $\leq 2\times 10^6$ | $s$ 中有且仅有两种字符 | $10$ | - | | $6$ | $\leq 3\times 10^5$ | 无 | $15$ | $1,2$ | | $7$ | $\leq2\times 10^6$ | 无 | $15$ | $1\sim 6$ | | $8$ | $\leq 5\times10^6$ | $\text{timelimit}=1.5s$ | $20$ | $1\sim 7$ | 对于 $100\%$ 的数据满足 $1\leq n\leq 5\times 10^6$，且 $s$ 仅包含小写英文字母和 ```?```。 除了 $\text{subtask 8}$ 之外，时限皆为 $1s$。 时间限制已开到了 std 的 2 倍以上，空间限制开到了 std 的 1.25 倍以上，但仍需 **注意程序的运行时空常数**。