16.3 用陣列儲存資訊：mex 函數

mex（minimum excludant）是競程的常客：給一堆非負整數，回傳沒出現過的最小非負整數。例如 \{3, 0, 1, 10, 3\} 的 mex 是 2——0 有、1 有、2 沒有，答案就是 2。

本站題目〈mex 函數〉：N \le 5 \times 10^5 個數字，0 \le a_i \le 10^9，求 mex。

直覺的做法：從 0 開始逐一檢查「0 出現過嗎？1 出現過嗎？……」，而每次檢查都把數列掃一遍——檢查一次 O(N)，最壞要檢查 N + 1 次，總共 O(N^2)：N = 5 \times 10^5 代進去是 2.5 \times 10^{11}，死當。