Sətir o zaman polindrom adlanır ki, o soldan sağa və sağdan sola eyni oxunsun. Məsələn, "abba" - polindromdur, "omax" isə yox. a sətri üçün onun j - i + 1 alt sətrini (i-dən j mövqeyə qədər) (mövqelər 1-dən başlayaraq nımrələnir) α[i..j] adlandıracağıq.
Uzunluğu n olan a sətri üçün polindrom olan q cütlüklərinin (i, j), 1 ≤ i < j ≤ n, belə ki, α[i..j] sajını tapmaq tələb olunur.
Kiçik latın hərfləri ehtiva edən n (1 ≤ n ≤ 10^5
) uzunluqda a sətri verilir.
Tələb olunan q cütlüklərinin sayı.