小红的前缀询问

题号：NC281405
时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld

题目描述

小红拿到了一个数组，她有若干次询问，每次询问一个前缀内有多少对相同的数。你能帮帮她吗？

如果存在 $i,j$ ， $1\leq i < j \leq n$ ，且 $a_i=a_j$ ，那么 $(a_i, a_j)$ 就是一对相同的数对。只要下标不同，就是不同的数对。

第一行输入一个正整数，代表数组大小。
第二行输入个正整数，代表小红拿到的数组。
。

输出个整数，第个整数代表前缀内有多少对相同的数。

示例1

复制

6
2 3 3 3 1 2

复制

0 0 1 3 3 4

对于前缀 [2]，没有相同的数。
对于前缀 [2,3]，没有相同的数。
对于前缀 [2,3,3]，有1对相同的数。
对于前缀 [2,3,3,3]，有3对相同的数。
对于前缀 [2,3,3,3,1]，有3对相同的数。
对于前缀 [2,3,3,3,1,2]，有4对相同的数。