Tìm số bị thiếu trong 0..n bằng seen[]

Nguồn: Phước Hưng OJ

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

Đề bài

Cho $n$ số nguyên phân biệt

được lấy từ tập

Tập $U$ có $n+1$ phần tử nhưng mảng chỉ chứa $n$ giá trị phân biệt, vì vậy tồn tại duy nhất một số

không xuất hiện trong mảng. Hãy tìm $m$ bằng tư duy đánh dấu hiện diện (seen[]).

Input

Dòng đầu chứa $n$. Dòng thứ hai chứa $n$ số nguyên phân biệt $a_i$ với $0\le a_i\le n$.

Output

In số nguyên duy nhất $m$ không xuất hiện trong mảng.

Subtask

Subtask 1 (20 điểm): $1\le n\le10$.

Subtask 2 (30 điểm): $1\le n\le5000$.

Subtask 3 (50 điểm): $1\le n\le2\cdot10^5$.

Ví dụ

Input

5
3 0 1 5 2

Output

4

Giải thích

Trong tập $\{0,1,2,3,4,5\}$, mảng đã chứa $0,1,2,3,5$, nên số duy nhất bị thiếu là $4$.