Nhàm chán (Boredom)

Nguồn: Codeforces

Phiên bản: Phước Hưng OJ Extended

Đề bài

Cho dãy $a$. Mỗi bước chọn một phần tử có giá trị $x$, nhận $x$ điểm, đồng thời mọi phần tử có giá trị $x-1$ và $x+1$ bị xóa. Có thể tiếp tục chọn các phần tử còn lại. Hãy tối đa hóa tổng điểm.

Input

Dòng 1 chứa $n$. Dòng 2 chứa $a_1,\ldots,a_n$.

Output

In tổng điểm lớn nhất.

Subtask

• Subtask 1 — 20 điểm: n <= 20; a_i <= 30. Mức này dành cho cách trực tiếp hoặc đệ quy nhỏ.
• Subtask 2 — 30 điểm: n <= 5000; a_i <= 5000. Mức này yêu cầu nhận ra trạng thái DP và loại bỏ tính toán lặp.
• Subtask 3 — 50 điểm: 1 <= n <= 100000; 1 <= a_i <= 100000. Đây là toàn bộ giới hạn của bài.

Ví dụ

Input

3
1 2 3

Output

4

Giải thích

Chọn các giá trị 1 và 3 cho tổng $1+3=4$ tốt hơn chọn 2 được 2 điểm.