{"raw_statement":[{"iden":"statement","content":"元旦联欢会即将到来，老师提前调查了班里 $n$ 名同学中第 $i$ 位同学喜欢的零食编号是 $a_{i}$。为了统计同学们喜爱零食的相似程度，老师定义了如下指标：一个序列的权值被定义为满足 $a_{i}=a_{j}$ 的下标对 $(i, j)$（其中 $i<j$）的数量。例如，序列 $a=[1,1,2,2,1]$ 的权值为 4，具有相同值的下标对为 $(1,2)$、$(1,5)$、$(2,5)$ 和 $(3,4)$。\n\n对于一个长度为 $n$ 的零食喜好序列 $a$，请你帮老师求出**所有子段**的权值之和。\n\n如果序列 $b$ 可以通过从序列 $a$ 的开头删除若干（可能为零或全部）元素，并从结尾删除若干（可能为零或全部）元素得到，则称 $b$ 是 $a$ 的一个子段。"},{"iden":"input","content":"第一行包含一个整数 $n$（$1 \\leq n \\leq 10^{5}$）。\n\n第二行包含 $n$ 个整数 $a_{1}, a_{2}, \\cdots, a_{n}$（$1 \\leq a_{i} \\leq 10^{9}$）。"},{"iden":"output","content":"输出一个整数，表示序列的所有子段的权值之和。"},{"iden":"note","content":"样例 1 解释：\n\n长度为 1 的子段不可能有满足条件的下标对，而序列所有长度大于 1 的子段为：\n- 第一组：$[1,2]$，0 个满足条件的下标对；\n- 第二组：$[1,2,1]$，1 个满足条件的下标对（$(1,3)$）；\n- 第三组：$[1,2,1,1]$，3 个满足条件的下标对（$(1,3)$、$(1,4)$、$(3,4)$）；\n- 第四组：$[2,1]$，0 个满足条件的下标对；\n- 第五组：$[2,1,1]$，1 个满足条件的下标对（$(2,3)$）；\n- 第六组：$[1,1]$，1 个满足条件的下标对（$(1,2)$）；\n\n总计：$0 + 1 + 3 + 0 + 1 + 1 = 6$。\n\n数据范围：\n\n对于前 30% 的数据，满足 $n \\leq 1000$；\n\n对于另外 20% 的数据，满足输入的 $a_{i}$ 互不相等；\n\n对于另外 20% 的数据，满足输入的 $a_{i}$ 全部相等；\n\n对于 100% 的数据，满足“输入格式”中给出的数据范围。\n"}],"translated_statement":null,"sample_group":[["4\n1 2 1 1","6"]],"show_order":[],"formal_statement":null,"simple_statement":null,"has_page_source":false}