Bài toán: Số nguyên dương nhỏ nhất còn thiếu

Cho một dãy số nguyên ~A~ gồm ~n~ phần tử ~a_1, a_2, \dots, a_n~.

Hãy tìm số nguyên dương nhỏ nhất không xuất hiện trong dãy ~A~.

Dữ liệu vào

• Dòng thứ nhất chứa số nguyên dương ~n~.
• Dòng thứ hai chứa ~n~ số nguyên ~a_1, a_2, \dots, a_n~.

Dữ liệu ra

• Ghi ra một số nguyên duy nhất là kết quả tìm được.

Ví dụ

Ví dụ 1:

• Đầu vào:

5
3 -1 1 4 1

• Đầu ra:

2

Ví dụ 2:

• Đầu vào:

4
1 2 3 4

• Đầu ra:

5

Ràng buộc

• ~1 \le n \le 10^6~.
• ~-10^9 \le a_i \le 10^9~.
• Subtask 1 (40% số điểm): ~n \le 10^3~ và ~-10^3 \le a_i \le 10^3~.
• Subtask 2 (30% số điểm): ~n \le 10^5~ và ~1 \le a_i \le 10^5~.
• Subtask 3 (30% số điểm): Không có ràng buộc gì thêm.

Gợi ý

• Áp dụng nguyên lý Dirichlet: Dãy chỉ có ~n~ phần tử nên số nguyên dương nhỏ nhất còn thiếu chắc chắn nằm trong đoạn ~[1, n + 1]~.
• Chỉ cần sử dụng một mảng đánh dấu boolean có kích thước ~n + 2~ để ghi nhận các giá trị ~a_i \in [1, n]~.