Double Palindrome

Time limit2sMemory limit1024 MB

Summary

Counts substrings of s that split into two equal-length halves, where each half is a palindrome, with n up to 500000.

Level: Hard9 of 10
Topics: String, String matching, Dynamic programming
Solved: No attempts yet

Problem

Vanya works at a factory that produces palindromes. The factory has a workpiece, a string $s$ of length $n$ made of lowercase English letters, and Vanya can cut out any substring of it for sale. A palindrome is a string that reads the same from left to right and from right to left.

Many people are tired of ordinary palindromes, so Vanya decided to produce double palindromes instead. A double palindrome is a concatenation of two palindromes of equal length. For example, aabb and aaaa are double palindromes, while abba and aaaabb are not.

Vanya wonders how many ways there are to cut out a double palindrome from $s$ . In other words, count the pairs $(l, r)$ such that the substring $s_l s_{l+1} \ldots s_r$ is a double palindrome.

Input

The first line contains an integer $n$ ( $1 \leq n \leq 500\,000$ ), the length of the string $s$ . The second line contains the string $s$ , consisting of lowercase English letters.

Output

Print a single integer, the number of double palindrome substrings.

Hint

In the first example, there are 5 double palindromes of length 2 (ab, ba, ac, ca and ac), and the whole string is a double palindrome as well (abacac).

Examples2

Example 1
Input
```
6
abacac
```
Expected output
```
6
```
Example 2
Input
```
5
aaaaa
```
Expected output
```
6
```