Dàn đèn trang trí có ~N~ bóng đèn được đánh số từ ~1~ đến ~N~, khi bật sáng thì bóng đèn thứ ~i~ có màu là ~a_i~ (~1 \leq a_i \leq N~). Trong một chu kỳ ~N~ giây, ở giấy thứ ~i~ (~1 \leq i \leq N~) thì bóng đèn thứ ~i~ được tắt và tất cả các bóng đèn còn lại được bật sáng.

Yêu cầu: Tại mỗi thời điểm của chu kỳ ~N~ giây, tính số lượng các cặp bóng đèn được bật sáng có cùng màu biết rằng hai cặp được xem là khác nhau khi có ít nhất một vị trí khác nhau.

Input

Vào từ file văn bản BAI4.INP gồm có:

• Dòng đầu tiên ghi số nguyên dương ~N~;
• Dòng thứ hai ghi ~N~ số nguyên dương ~a_1, a_2,..., a_n~, các số ghi cách nhau một dấu cách.

Output

Ghi ra file văn bản BAI4.OUT gồm ~N~ số trên một dòng lần lượt là số lượng cặp bóng đèn tìm được tại mỗi thời điểm của chu kỳ.

Scoring

• Subtask ~1~ ~(40\%)~: ~N \leq 200~;
• Subtask ~2~ ~(30\%)~: ~200 < N \leq 10000~;
• Subtask ~3~ ~(30\%)~: ~10000 < N \leq 200000~.

Example input 1

6
1 1 2 1 3 2

Example output 1

2 2 3 2 4 3