Description

给定一个数列 a1, a2, ..., an，请求出在这个序列中，存在多少个三元序列。 所谓"三元序列"，就是从数列中挑出三个数 ai, aj, ak，满足 i < j < k 且 ai = ak 且 ai ≠ aj。

Input

第一行：单个整数 n 第二行：n 个整数表示 a1, a2, ..., an

30% 的数据，n ≤ 100

60% 的数据，n ≤ 20,000

100% 的数据，1 ≤ n ≤ 300,000

0 ≤ ai < n

Output

单个整数：表示三元序列的数量。

Samples

6
1 1 2 2 1 1

8