题目描述

给定一个数列 $a_1,a_2,\dots,a_n$，请求出在这个序列中，存在多少个夹心饼干。

所谓夹心饼干，就是从数列中挑出三个数 $a_i,a_j,a_k$，满足 $i<j<k$ 且 $a_i=a_k$ 且 $a_i\neq a_j$。

输入格式

• 第一行：单个整数 $n$
• 第二行：$n$个整数表示 $a_1,a_2,\dots,a_n$

输出格式

• 单个整数：表示夹心饼干的数量。

5
1 2 1 2 1

5

数据范围

• $30\%$ 的数据，$n\leq100$
• $60\%$ 的数据，$n\leq20000$
• $100\%$ 的数据，$1\leq n\leq300,000$
• $0\leq a_i<n$