题目描述

白兔喜欢序列。但是，白兔不喜欢重复的序列。 什么叫重复的序列呢? 对于两个序列 $A[1 \ldots n], B[1 \ldots m]$ ， 如果满足以下条件，则称他们为等价序列:

• $n=m$
• 对于任意 $x, y \in[1, n]$ ，如果 $A[x]=A[y]$ ，则 $B[x]=B[y]$
• 对于任意 $x, y \in[1, n]$ ，如果 $B[x]=B[y]$ ，则 $A[x]=A[y]$

现在，白云有一个序列，白兔想从中挑选一个连续的子段。白兔想知道自己有多少种挑的方法。 因为白兔不喜欢重复的序列，所以，如果两种方法得到的序列是等价的，则只记为一种方案。

输入格式

第一行一个整数 $n$ 表示白云的序列长度 接下来一行 $n$ 个正整数 $P[1 \ldots n]$ 表示序列

输出格式

输出方案数

3 1 2 3

3

4 1 2 1 1

6

样例解释

对于样例一，所有长度为 1 的序列都等价、长度为 2 的序列都等价、长度为 3 的序列都等价 对于样例二，所有长度为 1 的序列都等价，长度为 2 的序列有 $[1,2],[1,1]$ 两种，长度为 3 的序列有 $[1,2,1],[2,1,1]$ 两种

输入样例 $3 / 4 / 5$

见下发文件

输出样例 $3 / 4 / 5$

见下发文件

数据范围与约定

• 对于 $20 \%$ 的数据， $n \leq 15$
• 对于 $40 \%$ 的数据, $n \leq 200$
• 对于 $60 \%$ 的数据， $n \leq 3000$
• 对于 $80 \%$ 的数据， $n \leq 10000$
• 对于 $100 \%$ 的数据， $P[i] \leq n \leq 50000$