Team Trees

All submissions for this problem are available.

### Read problem statements in [Bengali](http://www.codechef.com/download/translated/LTIME78/bengali/PLANT.pdf), [Mandarin Chinese](http://www.codechef.com/download/translated/LTIME78/mandarin/PLANT.pdf), [Russian](http://www.codechef.com/download/translated/LTIME78/russian/PLANT.pdf), and [Vietnamese](http://www.codechef.com/download/translated/LTIME78/vietnamese/PLANT.pdf) as well. You are given a string $S$ with length $N$. You should find two non-intersecting substrings of $S$ such that the second one is a substring of the first one and the product of these substrings' lengths is the maximum possible. More formally, let's denote a contiguous substring $S_l, S_{l+1}, \ldots, S_r$ by $S[l, r]$; you should find integers $l_1$, $r_1$, $l_2$ and $r_2$ which satisfy these four criteria: - $1 \le l_1 \le r_1 \le N$ and $1 \le l_2 \le r_2 \le N$ - $r_2 \lt l_1$ or $r_1 \lt l_2$ - $S[l_2, r_2]$ is a contiguous substring of $S[l_1, r_1]$ - the product $P = (r_2-l_2+1) \cdot (r_1-l_1+1)$ is maximum possible Find the maximum value of $P$. It is guaranteed that for the given test data, there is at least one way to choose $l_1, r_1, l_2, r_2$ such that the first three criteria are satisfied, i.e. the answer is well-defined. ### Input - The first line of the input contains a single integer $N$. - The second line contains a single string $S$ with length $N$. ### Output Print a single line containing one integer ― the maximum product $P$. ### Constraints - $1 \le N \le 2 \cdot 10^6$ - $S$ contains only lowercase English letters ### Subtasks **Subtask #1 (50 points):** $N \le 10^3$ **Subtask #2 (50 points):** original constraints ### Example Input 1 ``` 5 abaab ``` ### Example Output 1 ``` 6 ``` ### Explanation We can choose substrings $S[1, 2]$ and $S[3, 5]$. ### Example Input 2 ``` 25 atcodercodeforcescodechef ``` ### Example Output 2 ``` 76 ```