// 演算法：把所有數字放入雜湊集合，只從「沒有前一個數 (x-1)」的起點開始往上數，
// 累計每段連續序列的長度，取最大值。整體 O(n)。
// Algorithm: put all numbers in a hash set, then from each "start" (a value whose
// x-1 is absent) walk upward counting the run length; track the maximum. Overall O(n).

#include <stdlib.h>   // 提供 malloc / free / qsort 等 / provides malloc, free, etc.

// 為了在 C 裡有一個 O(1) 的「集合」，我們用開放定址雜湊表自己實作。
// To get an O(1) "set" in C, we build an open-addressing hash table ourselves.

#define EMPTY_SLOT 0x80000000  // 用一個不可能的整數標記空格 (此值超出題目範圍)
                               // A sentinel marking an empty slot (outside the input range).

// 把任意整數映射到表格索引 / map any integer to a table index.
static int hashIndex(long long key, int cap) {
    // key 可能是負數，先加上 cap 再取餘數，確保結果非負 / handle negatives: result stays in [0, cap).
    long long h = key % cap;
    if (h < 0) h += cap;
    return (int)h;
}

int longestConsecutive(int* nums, int numsSize) {
    if (numsSize == 0) return 0;  // 空陣列直接回傳 0 / empty input → 0.

    // 容量取 2 倍以上以降低碰撞；+1 避免容量為 0 / size table > 2x to keep collisions low.
    int cap = numsSize * 2 + 1;

    // 配置表格，每格存一個 int。malloc 回傳一塊未初始化記憶體的指標。
    // Allocate the table, one int per slot. malloc returns a pointer to raw memory.
    int* table = (int*)malloc(sizeof(int) * cap);

    // 把每一格初始化為 EMPTY_SLOT，表示目前是空的 / mark every slot empty first.
    for (int i = 0; i < cap; i++) table[i] = EMPTY_SLOT;

    // ---- 插入階段：把所有數字放進雜湊表，自動忽略重複 ----
    // ---- Insert phase: put every number into the table (duplicates harmlessly overwrite). ----
    for (int i = 0; i < numsSize; i++) {
        int v = nums[i];                 // 目前要插入的值 / the value to insert.
        int idx = hashIndex(v, cap);     // 算出它的起始格 / its starting slot.
        // 線性探測：若該格被別的值佔用，就往後一格找空位 (開放定址法)。
        // Linear probing: if the slot is taken by a different value, step to the next slot.
        while (table[idx] != EMPTY_SLOT && table[idx] != v) {
            idx = (idx + 1) % cap;       // % cap 讓索引繞回開頭 / wrap around to the front.
        }
        table[idx] = v;                  // 寫入值 (若已存在則原地覆寫，等於去重) / store (dups overwrite).
    }

    // ---- 查詢函式的內嵌寫法：用 lambda 在 C 不行，所以直接展開為一段探測迴圈 ----
    // In C there are no closures, so we inline the "contains" search where needed below.

    int longest = 1;  // 至少有一個元素，所以最短答案是 1 / at least one element exists → min 1.

    // ---- 主迴圈：對每個數字判斷它是不是序列起點 ----
    // ---- Main loop: for each number decide whether it starts a run. ----
    for (int i = 0; i < numsSize; i++) {
        int x = nums[i];

        // 檢查 x-1 是否存在：若存在，x 就不是起點，跳過以避免重複計算。
        // Check whether x-1 exists; if so, x is not a start, so skip (avoids redundant walks).
        long long prev = (long long)x - 1;   // 用 long long 防止 x = -2^31 時減 1 溢位 / avoid underflow.
        int pidx = hashIndex(prev, cap);
        int prevExists = 0;
        while (table[pidx] != EMPTY_SLOT) {  // 探測直到遇到空格才確定不存在 / probe until an empty slot.
            if (table[pidx] == (int)prev) { prevExists = 1; break; }
            pidx = (pidx + 1) % cap;
        }
        if (prevExists) continue;            // x-1 在 → x 不是起點 / x-1 present → not a start.

        // 到這裡 x 是某段序列的起點，開始往上數 x+1, x+2, ...
        // x is a run start: walk upward counting x+1, x+2, ...
        int curNum = x;       // 目前數到的數字 / the number we have reached.
        int curLen = 1;       // 這段的長度，從 1 起算 / current run length, starting at 1.

        while (1) {           // 無限迴圈，內部用 break 跳出 / loop until next number is absent.
            long long next = (long long)curNum + 1;  // 下一個要找的數 / the next value to look for.
            int nidx = hashIndex(next, cap);
            int found = 0;
            while (table[nidx] != EMPTY_SLOT) {       // 在表中搜尋 next / search for next in the table.
                if (table[nidx] == (int)next) { found = 1; break; }
                nidx = (nidx + 1) % cap;
            }
            if (!found) break;                        // 找不到下一個 → 這段結束 / chain ends.
            curNum = (int)next;                       // 接上，往上移動 / extend the chain.
            curLen++;                                 // 長度加一 / length grows by one.
        }

        if (curLen > longest) longest = curLen;       // 更新最長紀錄 / update the maximum.
    }

    free(table);   // 釋放 malloc 配置的記憶體，避免記憶體洩漏 / free the table to avoid a memory leak.
    return longest;
}