#P14084. 【哈希3】前缀查询问题

【哈希3】前缀查询问题

题目描述

给定一个长度为 nn 的数组 aa,数组中的每个元素都是正整数。我们需要回答 nn 个查询,第 ii 个查询是关于数组前缀 ai,a2,...,aia_i, a_2, ..., a_i 的:

对于每一个查询 ii,请你计算在前缀 ai,a2,...,aia_i, a_2, ..., a_i 中数字 ii 出现了多少次。

输入描述

第一行包含一个整数 nn (1n1051 \leq n \leq 10^{5}),表示数组的长度。

第二行包含 nn 个正整数 a1,a2,,ana_1, a_2, \dots, a_n (1ain1 \leq a_i \leq n),表示数组 aa

输出描述

输出 nn 个整数,第 ii 个整数表示数字 ii 在前缀 ai,a2,...,aia_i, a_2, ..., a_i 中出现的次数。

样例1

输入

5
1 2 1 3 2

输出

1 1 0 0 0

样例解释

前缀 [1] 中,数字 1 出现 1 次。

前缀 [1, 2] 中,数字 2 出现 1 次。

前缀 [1, 2, 1] 中,数字 3 出现 0 次。

前缀 [1, 2, 1, 3] 中,数字 4 出现 0 次。

前缀 [1, 2, 1, 3, 2] 中,数字 5 出现 0 次。