Cho một mảng a gồm n phần tử ~a_1~, ~a_2~, ... ~a_n~.

Gọi độ bất ngờ của x trong mảng a là số lần xuất hiện của x trong mảng a.

Bây giờ bạn hãy in ra độ bất ngờ của mỗi phần tử ~a_1~, ~a_2~, ... ~a_n~.

Input

Dòng duy nhất chứa một số nguyên n

Dòng thứ hai là dãy ~a_1, a_2, ... a_n ~

Subtask 1 (60% điểm): ~1 ≤ n ≤ 10^3, 1 ≤ a_i ≤ 10^3~

Subtask 2 (40% điểm): ~1 ≤ n ≤ 10^5, 1 ≤ a_i ≤ 10^5~

Output

Một dòng duy nhất là độ bất ngờ của mỗi phần tử ~a_1, a_2, ... a_n~.

Examples

Input

9 
1 3 2 4 5 1 2 2 5 

Output

2 1 3 1 2 2 3 3 2