Tìm Mex

Trong một buổi thảo luận về ứng dụng di động mới, FullHouse Dev đã nhận được một thử thách thú vị từ một nhà phát triển điện thoại thông minh. Họ được yêu cầu tạo ra một thuật toán để tính giá trị Mex cho một dãy số, như một phần của tính năng bảo mật mới cho ứng dụng. Với niềm đam mê công nghệ và tinh thần đổi mới, FullHouse Dev đã quyết định giải quyết bài toán này.

Bài toán

Cho một mảng số nguyên có độ dài \(n\). Nhiệm vụ của FullHouse Dev là tìm giá trị Mex cho mỗi phần tử thứ \(i\) trong mảng \((1 \leq i \leq n)\).

Mex của phần tử thứ \(i\) là số nguyên không âm nhỏ nhất lớn hơn hoặc bằng \(0\) mà không xuất hiện trong mảng từ chỉ số \(1\) đến \(i\).

INPUT FORMAT:

• Dòng đầu tiên chứa một số nguyên \(n\) - độ dài của mảng.
• Dòng thứ hai chứa \(n\) số nguyên - các phần tử của mảng.

OUTPUT FORMAT:

• In ra \(n\) số nguyên. Số thứ \(i\) là giá trị Mex của mảng con từ phần tử đầu tiên đến phần tử thứ \(i\).

Ràng buộc:

• \(1 \leq n \leq 10^5\)
• \(0 \leq a_i \leq 10^9\) (các phần tử trong mảng)

Ví dụ

INPUT

5
1 0 5 5 3

OUTPUT

0 2 2 2 2

Giải thích

• Mex của phần tử đầu tiên là 0, vì 0 không có trong mảng.
• Mex của hai phần tử đầu tiên là 2, vì 0 và 1 đã có trong mảng.
• Mex của ba, bốn và năm phần tử đầu tiên vẫn là 2, vì 0 và 1 vẫn là các số nhỏ nhất không có trong mảng con tương ứng.

FullHouse Dev đã giải quyết thành công bài toán này, chứng minh khả năng xử lý các vấn đề thuật toán phức tạp và sẵn sàng áp dụng vào việc phát triển các tính năng bảo mật tiên tiến cho ứng dụng di động.