Trong thư viện hiện đại của trường đại học X, sinh viên muốn đọc sách phải quét mã ID để mượn sách hoặc trả sách qua một hệ thống giám sát. Mã ID là một số nguyên dương mã hóa thông tin của sinh viên. Hệ thống sẽ ghi lại các mã số ID theo thứ tự thời điểm quét. Thời điểm đầu tiên được tính là ~1~ và tự động tăng 1 khi có sinh viên quét mã ID vào hệ thống. Hệ thống chỉ cho phép lưu trữ dữ liệu trong một ngày.
Một sinh viên có mã ID tồn tại trong hệ thống nhiều hơn ~1~ lần thì thời điểm đầu là ~i~ (mượn), thời điểm cuối là ~j~ (trả), ~j - i~ là khoảng thời gian đọc của sinh viên đó (nếu giữa thời điểm ~i~ và ~i~ có tồn mại mã ID tại thời điểm ~k~ ~(i < k < j)~ thì có thể xem là sinh viên đó mượn thêm sách khác). Ngược lại nếu mã ID của một sinh viên chỉ tồn tại ~1~ lần trong hệ thống thì khoảng thời gian đọc là ~0~.
Ví dụ hệ thống ghi nhận sinh viên quét mã ID trong ~10~ thời điểm như sau:
Thời điểm | ~1~ | ~2~ | ~3~ | ~4~ | ~5~ | ~6~ | ~7~ | ~8~ | ~9~ | ~10~ |
---|---|---|---|---|---|---|---|---|---|---|
ID | ~14~ | ~12~ | ~14~ | ~27~ | ~12~ | ~14~ | ~12~ | ~27~ | ~33~ | ~65~ |
- Sinh viên có ID ~= 12~ có thời điểm mượn sách lần đầu và trả sách lần cuối là ~2~ và ~7~ (thời điểm ~5~, ID ~= 12~ chỉ mượn thêm sách khác). Khoảng thời gian đọc là ~7 - 2 = 5~.
- Sinh viên có Id ~= 33~ quét mã ID tại thời điểm ~9~. Khoảng thời gian đọc là ~0~.
- Sinh viên có ID ~= 14~ có thời điểm mượn sách lần đâu và trả sách lần cuối là ~1~ và ~6~ (thời điểm ~3~, ID ~= 14~ chỉ mượn thêm sách khác). Khoảng thời gian đọc là ~6 - 1 = 5~.
- Sinh viên có ID ~= 65~ quét mã ID tại thời điểm ~10~. Khoảng thời gian đọc là ~0~.
- Sinh viên có ID ~= 27~ có thời điểm mượn sách lần đầu và trả sách lần cuối là ~4~ và ~8~. Khoảng thời gian đọc là ~8 - 4 = 4~.
Yêu cầu: Bạn hãy cho biết ID của sinh viên có khoảng thời gian đọc sách lớn nhất.
Dữ liệu vào
Nhập từ tập tin văn bản TIMELINE.INP
gồm ~2~ dòng:
- Dòng đầu tiên ghi số nguyên dương ~N~ ~(1 \le N \le 10^5)~ là số thời điểm hệ thống ghi nhận.
- Dòng thứ hai ghi ~N~ số nguyên ~a_1, a_2, ..., a_N~ ~(1 \le i \le N; 1 \le a_i \le 10^{18})~ là ID của các sinh viên.
Kết quả ra
Xuất ra tập tin văn bản TIMELINE.OUT
gồm ~2~ dòng:
- Dòng đầu tiên là ID của sinh viên có khoảng thời gian đọc sách lớn nhất.
- Dòng thứ hai là khoảng thời gian đọc sách lớn nhất của sinh viên có mã ID ở dòng ~1~.
Lưu ý: Nếu có nhiều ID cùng khoảng thời gian đọc lớn nhất thì xuất ID của sinh viên được tìm thấy đầu tiên.
Ví dụ
Dữ liệu vào
10
14 12 14 27 12 14 27 33 65
Kết quả
14
5
Giải thích
- Mã ID ~= 14~ và mã Id ~= 12~ có cùng khoảng thời gian đọc là ~5~ nhưng chỉ lấy ID xuất hiện đầu tiên là ~14~.
Bài tập được chấm trên bộ test tự sinh của CLAOJ
Bình luận