Có ~N~ thẻ, thẻ thứ ~i~ ghi số nguyên ~A_i~. Với mỗi vị trí ~k~ từ ~1~ đến ~N~, hãy tưởng tượng bỏ riêng thẻ thứ ~k~. Trong ~N - 1~ thẻ còn lại, cần đếm số cách chọn hai thẻ khác nhau sao cho hai số ghi trên chúng bằng nhau. Thứ tự chọn hai thẻ không tạo ra cách mới.

Hãy in đáp án cho mọi ~k~ theo thứ tự từ ~1~ đến ~N~.

Input

• Dòng đầu chứa số nguyên ~N~, là số lượng thẻ.
• Dòng thứ hai chứa ~N~ số nguyên ~A_1, A_2, ..., A_N~, trong đó ~A_i~ là số ghi trên thẻ thứ ~i~.

Output

• In ~N~ dòng; dòng thứ ~k~ là số cặp thẻ có giá trị bằng nhau sau khi bỏ thẻ thứ ~k~.

Giới hạn

• ~3 ≤ N ≤ 2 × 10^5~.
• ~1 ≤ A_i ≤ N~ với mọi ~1 ≤ i ≤ N~.
• Mọi giá trị đầu vào là số nguyên.

Ví dụ

Input

5
1 1 2 1 2

Output

2
2
3
2
3

Giải thích ví dụ

Nếu bỏ thẻ thứ nhất, dãy còn lại là 1, 2, 1, 2: có một cặp mang số 1 và một cặp mang số 2, nên kết quả là 1 + 1 = 2. Nếu bỏ thẻ thứ ba mang số 2, ba thẻ mang số 1 tạo ra 3 cặp, còn số 2 chỉ xuất hiện một lần, nên dòng thứ ba là 3.