Description

给定一个长度为n且仅包含小写英文字母的字符串S。

你有一个字符串T，初始为空串。

你可以进行n次操作，每次操作你可以在T的前端或末尾加入一个任意字母。

记第i次操作后T在S中的出现次数为fi，你需要最大化ans=∑ifi

Format

Input

第一行一个正整数n，表示字符串S的长度。

第二行一个长度为n的字符串S。

1≤n≤2×10^5

Output

如题

Samples

6
abcabc

9