Mã sự kiện chủ đạo

Bối cảnh

Một nền tảng giám sát nhận liên tiếp n mã sự kiện. Báo cáo cuối ca cần xác định "mã chủ đạo" — mã xuất hiện nhiều nhất. Nếu nhiều mã có cùng tần suất, đội vận hành ưu tiên mã xuất hiện sớm hơn trong log vì đó là tín hiệu có khả năng khởi phát sự cố trước. Nếu vẫn cần một quy tắc quyết định cuối cùng, giá trị mã nhỏ hơn được ưu tiên.

Bài toán không được sort vì B15 chưa học thuật toán sắp xếp. Thay vào đó, bạn cần chọn representation phù hợp: map để đếm frequency và ghi first index, còn thứ tự thời gian có thể được đọc trực tiếp theo index của input. Sau khi thu thập đủ thống kê, duyệt các key trong map để chọn ứng viên tốt nhất theo ba tiêu chí. Điểm khó của bài Medium nằm ở việc mô hình hóa tie-break rõ ràng và không nhầm "key nhỏ nhất" của map với "xuất hiện sớm nhất" trong dữ liệu.

Yêu cầu

1. Đọc n mã sự kiện.
2. Đếm tần suất và lưu index xuất hiện đầu tiên của từng mã.
3. Chọn mã có frequency lớn nhất; tie theo first index nhỏ hơn; nếu còn tie, mã nhỏ hơn.
4. In code frequency firstIndex.

Input

Dòng 1 n. Dòng 2 n số nguyên.

Output

Một dòng code frequency firstIndex.

Ràng buộc

1≤n≤5000, |code|≤10^9.

Ví dụ 1

Input

8
5 1 5 2 1 5 2 3

Output

5 3 0

Giải thích

Mã 5 xuất hiện ở index 0,2,5 nên frequency=3; mã 1 và 2 mỗi mã chỉ xuất hiện 2 lần, còn 3 xuất hiện 1 lần. Vì 3 là tần suất lớn nhất tuyệt đối, không cần dùng tie-break. First index của 5 là 0, nên output là 5 3 0.

Ví dụ 2

Input

6
4 2 4 2 3 3

Output

4 2 0

Giải thích

Các mã 4,2,3 đều xuất hiện đúng 2 lần. Khi frequency bằng nhau, ta so first index: 4 xuất hiện lần đầu ở index 0, 2 ở index 1, 3 ở index 4. Vì 0 nhỏ nhất, mã 4 được chọn dù map tự sắp key theo giá trị. Output là 4 2 0.

Thông tin học tập

• Module: M05
• Buổi: B15
• Loại bài: HOMEWORK
• Độ khó: Medium
• Concepts: vector, map, frequency, first occurrence, tie-break
• Giới hạn kiến thức: B01-B15
• Time limit: 1 second(s)
• Memory limit: 256 MB
• Point: 100