Polindromlar 2

Bir sətrin palindrom adlandırılması üçün, o, soldan sağa və sağdan sola eyni oxunmalıdır. Məsələn, abba palindromdur, amma omax deyil. Verilmiş $\alpha$ sətri üçün, $\alpha [i..j]$ onun $i$-ci mövqedən başlayıb $j$-ci mövqedə bitən (hər ikisi daxil olmaqla), uzunluğu j - i + 1 olan hissə-sətrini işarə edir, burada mövqelər $1$-dən başlayaraq nömrələnir.

Uzunluğu $n$ olan bir $\alpha$ (1 \leq n \leq 5\,000\,000) sətri verilib, 1 \leq i < j \leq n şərti ilə elə cüt $(i,j)$-lərin sayını tapın ki, $\alpha [i..j]$ hissə-sətiri palindrom olsun.