题目描述

Two strings $u_1 u_2 \dots u_k$ and $v_1 v_2 \dots v_l$ are isomorphic if and only if k = l and there exists a injection $\phi$ such that $u_i = \phi(v_i)$ for all $i \in \{1, 2, \dots, k\}$. Note that a function f is injection if and only if $f(x) \neq f(y)$ for all $x \neq y$.

Bobo would like to choose some strings from all $\frac{n(n + 1)}{2}$​ substrings of the given string $s_1 s_2 \dots s_n$ . Find out the maximum number of strings he may choose so that no two chosen strings are isomorphic.

输入格式

The input consists of several test cases and is terminated by end-of-file.

The first line of each test case contains an integer n. The second line contains a string $s_1, s_2, \dots, s_n$.

• $1 \leq n \leq 5\times 10^4$
• $1 \leq s_i \leq n$
• There are at most $10^3$ test cases, and at most 5 of them have n > 50.

输出格式

For each test case, print an integer which denotes the result.

样例

样例输入 1

3
1 2 3
3
1 2 2
5
1 3 1 2 5

样例输出 1

3
4
7