Độ khó: Trung bình (2/4 điểm)

📖 Bài giải chi tiết: 👉 Bấm vào đây để xem lời giải cụ thể của bài này trên blog

⚠️ Lưu ý: hãy đảm bảo em đã thật sự cố gắng tự làm bài trước, rồi mới bấm vào xem bài giải nhé!

🎓 Khóa học Lập trình Thuật toán thi đấu của thầy Nguyễn Việt Nam Sơn – 111 buổi video, kèm cặp cá nhân, luyện thi chuyên Tin · HSG Tin học · Tin học trẻ · đội tuyển quốc gia · Olympic/ICPC. 👉 Xem chi tiết khóa học · Thành tích học viên

📞 Đăng ký học: Zalo 0767 666 702 · Facebook Nguyễn Việt Nam Sơn · 🌐 laptrinhthuattoan.blogspot.com

Sắn không thích sự nhàm chán. Đó là lý do tại sao bất cứ khi nào cậu ta buồn chán, cậu ta nghĩ ra các trò chơi. Một buổi tối mùa đông dài, cậu nghĩ ra một trò chơi và quyết định chơi nó.

Cho một dãy ~a~ gồm ~n~ số nguyên. Người chơi có thể thực hiện một số bước. Trong một bước duy nhất có thể chọn một phần tử của dãy là ~a_k~ và xóa nó, sau đó tất cả các phần tử bằng với ~a_k + 1~ và ~a_k - 1~ cũng phải bị xóa khỏi dãy. Bước đó mang lại ~a_k~ điểm cho người chơi.

Sắn là người cầu toàn, vì vậy anh quyết định lấy càng nhiều điểm càng tốt. Bạn hãy giúp anh ta tính xem trong trường hợp chơi tốt nhất thì anh ta có bao nhiêu điểm.

Dữ liệu vào

• Dòng đầu tiên chứa số nguyên ~n~ ~(1 \le n \le 10^5)~ cho biết có bao nhiêu số trong dãy của Sắn.
• Dòng thứ hai chứa ~n~ số nguyên ~a_1, a_2, \ldots, a_n~ ~(1 \le a_i \le 10^5)~.

Kết quả

• In một số nguyên duy nhất – số điểm tối đa mà Sắn có thể kiếm được.

Sample Input 1

2
1 2

Sample Output 1

2

Sample Input 2

3
1 2 3

Sample Output 2

4

Sample Input 3

9
1 2 1 3 2 2 2 2 3

Sample Output 3

10

Nguồn: VinhDinhCoder.