405189: GYM101821 D Search Engine

As you probably know, the main product of Yandex is its search engine, which we will consider in this problem.

In this problem, search engine operates on a database, which can be represented as a string s of length n. The System allows users to search arbitrary text in a database, as a result of the search, system displays a list of request's occurrences, alongside the number of them. An occurrence means that query text appears in a database as a substring.

Alice is bored, and so she tries to entertain herself. She has opened the search engine, which shows the empty text field initially.

Then Alice repeatedly modifies the previous request by either appending or prepending a new letter to it, and then she repeats the search. Alice performs this operation exactly n times.

The entertaining part of the process is observation process of the number of occurencies displayed by the system — it may decrease a lot after one iteration. Or may not.

Alice decided to test whether the search engine will continue to work fast if required to output a lot of data, so she decided to make her requests in such a way that the sum of occurrences of all n requests in s will be maximum possible. What is the largest possible sum she can achieve?

The first line of the input contains a single integer n (1 ≤ n ≤ 200 000) — the length of the string s.

The second line contains the string s composed of English lowercase letters only.

Output a single integer — largest possible total number of occurences.

5
aaaaa

15

6
abcabc

9

The request sequence "a"  →  "aa"  →  "aaa"  →  "aaaa"  →  "aaaaa" gives the total number of 15 = 1 + 2 + 3 + 4 + 5 occurrences.

One of the optimal sequences for the second sample is "a"  →  "ab"  →  "abc"  →  "cabc"  →  "bcabc"  →  "abcabc" gives 9 = 2 + 2 + 2 + 1 + 1 + 1 occurrences in total.