问题描述

小红有一个长度为$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$。

输出格式

输出一个整数表示答案。

样例

6
1 2 1 2 2 1

5

样例说明

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

数据范围

对于全部测试数据，$1\le n \le 10^5$，$1 \le a_i \le 10^9$