Cho dãy \(N\) số nguyên dương \(A_1\), \(A_2\),..., \(A_N\). Bạn hãy đếm số lượng bộ ba chỉ số \((i,j,k)\) đồng thời thỏa hai điều kiện:

• \(1\le i < j < k \le N\),
• \(A_i=A_k\ne A_j\).

Input

• Dòng đầu chứa số nguyên dương \(N\) \(\left(3\le N\le 3\times 10^5\right)\).
• Dòng tiếp theo chứa \(N\) số nguyên dương \(A_1\), \(A_2\),..., \(A_N\) \(\left(1\le A_i\le N\right)\).

Output

• Gồm \(Q\) dòng là câu trả lời cho \(Q\) truy vấn tương ứng.

Ví dụ

Sample input 01

5
1 2 1 3 2

Sample output 01

3

Giải thích

Các bộ ba chỉ số thỏa mãn đề bài là:

• \((1,2,3)\)
• \((2,3,5)\)
• \((2,4,5)\)

Sample input 02

13
9 7 11 7 3 8 1 13 11 11 11 6 13

Sample output 02

20

Sample input 03

8
1 2 3 4 5 6 7 8

Sample output 03

0