// 演算法：把所有數字放進 unordered_set (雜湊集合)，只從「x-1 不存在」的起點往上數，
// 累計每段連續序列長度並取最大。整體 O(n)。
// Algorithm: load all numbers into an unordered_set, walk upward only from run-starts
// (values whose x-1 is absent), track the longest run. Overall O(n).

#include <vector>          // std::vector 動態陣列 / dynamic array.
#include <unordered_set>   // std::unordered_set 雜湊集合，O(1) 平均查詢 / hash set, O(1) average lookup.
#include <algorithm>       // std::max 取較大值 / for std::max.
using namespace std;

class Solution {
public:
    int longestConsecutive(vector<int>& nums) {
        // 用 nums 的頭尾迭代器一次建好集合；重複值會自動被忽略。
        // Build the set directly from nums's begin/end iterators; duplicates are dropped automatically.
        unordered_set<int> s(nums.begin(), nums.end());

        int longest = 0;  // 答案；空陣列時保持 0 / answer; stays 0 for empty input.

        // range-for：依序取出集合中每個元素 x (此處用 const 參考避免複製)。
        // range-for: iterate over each element x in the set (const reference avoids copying).
        for (const int x : s) {
            // s.count(x-1) 回傳 0 或 1，代表 x-1 在不在集合裡。
            // s.count(x-1) returns 0 or 1: whether x-1 is present.
            // 若 x-1 存在，x 不是起點，跳過 / if x-1 exists, x is not a start, skip.
            if (s.count(x - 1)) continue;

            // x 是序列起點，開始往上數 / x starts a run; walk upward.
            int curNum = x;     // 目前到達的數字 / current value reached.
            int curLen = 1;     // 本段長度 / current run length.

            // 只要下一個數還在集合裡就繼續延伸 / keep extending while the next value exists.
            while (s.count(curNum + 1)) {
                curNum++;       // 移到下一個連續數 / move to the next consecutive number.
                curLen++;       // 長度加一 / grow the length.
            }

            longest = max(longest, curLen);  // 更新最長紀錄 / keep the maximum.
        }

        return longest;
    }
};