Trong một cuộc thi ăn kem được tổ chức trong câu lạc bộ EEEC, mỗi thành viên tham gia cuộc thi sẽ được đánh số thứ tự từ \(0\) đến \(n\), thành viên thứ \(i\) đạt thành tích \(a_i\) . Biết rằng ai ăn được càng nhiều thì xếp hạng sẽ càng cao.

Ban tổ chức muốn chọn ra ba số điểm cao nhất để trao giải, hãy đếm xem trong số những thành viên tham gia có bao nhiêu người đạt số điểm cao nhất, thứ hai và thứ ba.

Input:

• Dòng đầu tiên 1 số nguyên \(n\) \((3 ≤ n ≤ 10^6)\)
• Dòng thứ hai bao gồm \(a_0, a_1, ..., a_n\) \((1 ≤ a_i ≤ 10^4)\)

Output:

• Số lượng thành viên được đứng thứ hạng \(1\), \(2\) và \(3\)

Lưu ý: In kết quả theo dạng

1st: x
2nd: x
3rd: x

Với x là số thành viên đạt được của mỗi bậc hạng.

Example

Input1:

6
50 100 200 50 30 200

Output1:

1st: 2
2nd: 1
3rd: 2

Giải thích: