Cho một dãy gồm \(N\) số nguyên \((1 \le N \le 10^5, -10^9 \le A_i \le 10^9)\). Hãy đếm số lần xuất hiện của mỗi số. Sau đó, in ra các cặp (giá trị, tần suất) theo thứ tự giá trị tăng dần.

Input

• Dòng đầu tiên là số nguyên dương \(N\).
• Dòng thứ hai là \(N\) số nguyên \(a_1, a_2, \ldots, a_n\), mỗi số cách nhau một dấu cách.

Output

Với mỗi giá trị \(x\) xuất hiện trong dãy, in ra một dòng theo định dạng \(x: tan_suat\). Các dòng được in theo thứ tự giá trị \(x\) tăng dần.

Sample Input

7
10 -20 10 30 -20 10 -20

Sample Output

-20: 3
10: 3
30: 1

Subtask

• 30%: \(N \le 100\)
• 30%: \(N \le 5000\)
• 40%: Không có ràng buộc bổ sung