题目内容

小塔有一个长度为$n$的数组$a$，记$f(l,r,x)$为区间[$l,r$]内$x$的出现次数。

现在小塔想知道有多少对$i<j$满足$f(1,i,a_i)>f(j,n,a_j)$。

输入描述

第一行输入一个整数 $n$

第二行$n$个整数$a_1,a_2,...,a_n$。

$1≤n≤10^5$

$1≤a_i≤10^9$

输出描述

输出一个整数表示答案。

样例1

输入

6
1 2 1 2 2 1

输出

5

说明

存在以下五对($i,j$)满足条件：$(3,5)(3,6)(4,5)(4,6)(5,6)$

样例2

输入

输出