Tết đang đến gần, gia đình của Tèo có ~K~ công việc nhà cần phải hoàn thành như dọn dẹp nhà cửa, trang trí, chuẩn bị đồ ăn và mua quà, ....Gia đình Tèo gồm ~N~ thành viên, mỗi thành viên của gia đình được đánh số từ ~1~ đến ~N~. Mỗi công việc sẽ có duy nhất ~1~ người đã thành thạo làm công việc đó và sẽ có giá trị là ~a_i~ ~(1 \le a_i \le N)~ tương ứng với người có thứ tự ~a_i~ thành thạo công việc đó.
Thời gian hoàn thành một công việc của một thành viên là ~2~ giờ, nhưng nếu công việc đó là công việc mà thành viên đó thành thạo thì thời gian sẽ giảm đi một nửa, tức là ~1~ giờ.
Gia đình Tèo muốn phân chia công việc sao cho tất cả công việc được hoàn thành nhanh nhất. Hãy giúp họ tìm ra cách phân chia công việc cho các thành viên trong gia đình để thành viên hoàn thành tất cả công việc được giao lâu nhất có tổng thời gian hoàn thành là ít nhất.
Yêu cầu: Tính thời gian hoàn thành tất cả các công việc ít nhất của người hoàn thành lâu nhất.
Lưu ý:
- Mỗi công việc chỉ được phân cho duy nhất ~1~ người.
- Không nhất thiết tất cả mọi thành viên đều phải làm việc nhà.
- Đề bài đảm bảo luôn có một kết quả duy nhất thoả mãn điều kiện đề bài.
Dữ liệu vào
- Dòng đầu tiên chứa 2 số nguyên dương ~N~ và ~K~ ~(1 \le N \le K \le 2 \times 10^5)~.
- Dòng thứ hai chứa một dãy số nguyên ~a_1, a_2, ..., a_K~ ~(1 \le a_i \le N)~.
Dữ liệu ra
- Một dòng duy nhất chứa một số nguyên là kết quả của đề bài.
Giới hạn
- Subtask ~1~ ~(50\%)~: ~N,K \le 10^4~.
- Subtask ~2~ ~(50\%)~: Không có ràng buộc gì thêm.
Ví dụ
Dữ liệu vào 1
3 5
1 2 3 3 1
Dữ liệu ra 1
2
Giải thích
- Công việc của người thứ ~1~: ~1~ và ~5~. Thời gian hoàn thành là ~2~.
- Công việc của người thứ ~2~: ~2~. Thời gian hoàn thành là ~1~.
- Công việc của người thứ ~3~: ~3~ và ~4~. Thời gian hoàn thành là ~2~.
~\Rightarrow~ Thời gian hoàn thành công việc của người hoàn thành lâu nhất là ~2~.
Dữ liệu vào 2
3 3
1 1 1
Dữ liệu ra 2
2
Giải thích
- Công việc của người thứ ~1~: ~1~. Thời gian hoàn thành là ~1~.
- Công việc của người thứ ~2~: ~2~. Thời gian hoàn thành là ~2~.
- Công việc của người thứ ~3~: ~3~. Thời gian hoàn thành là ~2~.
~\Rightarrow~ Thời gian hoàn thành công việc của người hoàn thành lâu nhất là ~2~.
Comments