// 演算法 / Algorithm:
// 1) 一次掃描找出最長連續前綴的總和 s（相鄰相差 1 才延伸）。
//    One pass to sum the longest sequential prefix (extend only when neighbours differ by 1).
// 2) 把所有值放進 unordered_set，從 s 往上找第一個不在集合裡的整數。
//    Put all values in an unordered_set, then scan up from s for the first missing integer.

#include <vector>
#include <unordered_set>
using namespace std;

class Solution {
public:
    int missingInteger(vector<int>& nums) {
        // s 從第一個元素起算；陣列非空，單元素前綴必為連續。
        // Start s at nums[0]; the array is non-empty and a single element is always sequential.
        int s = nums[0];

        // 從下標 1 開始嘗試延長連續前綴。
        // From index 1, try to extend the sequential prefix.
        for (int i = 1; i < (int)nums.size(); i++) {
            if (nums[i] == nums[i - 1] + 1)   // 剛好比前一個大 1 才算連續 / exactly one greater
                s += nums[i];                 // 累加進總和 / add to the sum
            else
                break;                        // 斷裂就停止 / stop at the first break
        }

        // unordered_set：雜湊集合，可用 count() 在近乎 O(1) 時間判斷值是否存在。
        // unordered_set: a hash set giving near-O(1) membership checks via count().
        // 用範圍 for 迴圈把每個值插入集合（begin..end 逐一走訪）。
        // Range-for loop inserts every value (iterates each element in turn).
        unordered_set<int> seen(nums.begin(), nums.end());

        // 從 s 開始遞增，直到找到一個不在集合裡的整數。
        // Increment from s until we hit an integer that is not in the set.
        int x = s;
        // count(x) 回傳 x 在集合裡的個數（0 或 1）；為 1 表示存在，需繼續往上找。
        // count(x) returns how many times x is in the set (0 or 1); 1 means present, so keep going.
        while (seen.count(x)) {
            x++;   // 這個數已存在，換下一個 / this value exists, move to the next
        }

        return x;   // 大於等於 s 的最小缺失整數 / smallest missing integer >= s
    }
};