#P2062. 学姐给你们出的签到题

学姐给你们出的签到题

题目描述

何小猪拿到了一个数组,她有若干次询问,每次询问一个前缀内有多少对相同的数,你能帮帮她吗?
如果存在一对i,ji,j(1i<jn)(1\le i<j \le n),且Ai=AjA_{i}=A_{j},那么(Ai,Aj)(A_{i},A_{j})就是一对相同的数对
Tip:只要有一个下标不同,就是属于不同的数对

输入格式

第一行输入一个正整数nn,代表数组大小。(1n106)(1 \le n \le 10^{6})
第二行输入nn个正整数AiA_{i} ,代表小红拿到的数组,(1Ai106)(1 \le A_{i} \le 10^{6})

输出格式

输出nn个整数,第ii个整数代表前缀[1,i][1,i]内有多少对相同的数。

样例

6
2 3 3 3 1 2
0 0 1 3 3 4