// Algorithm: BFS over indices. Edges = (i-1, i+1, all j with arr[i]==arr[j]).
// Pre-build a hash map value -> indices. First time we expand any index of value v,
// enqueue every same-value index and then CLEAR that bucket so we never rescan it.
// Without this clearing, inputs like [7,7,...,7] would cost O(n^2) and TLE.

#include <stdio.h>     // 標準 I/O / standard I/O
#include <stdlib.h>    // malloc, calloc, free / 動態記憶體
#include <string.h>    // memset (備用 / just in case)

#define HASH_SIZE 100003                              // 質數桶數，降低碰撞 / prime bucket count, fewer collisions

// 雜湊表的一個節點：保存某個 value，以及所有等於該 value 的索引清單
// One hash-table node: stores a value and the list of indices that hold that value
typedef struct Bucket {
    int value;              // 鍵：陣列中的數值 / key: the integer value
    int *idx;               // 值：索引動態陣列 / dynamic array of indices
    int count;              // 目前有幾個索引 / current size
    int cap;                // 容量 / capacity for realloc
    struct Bucket *next;    // 同一個桶內的鏈結 / chaining for collisions
} Bucket;

// 簡單的整數雜湊：把 int 攪一攪後取模 / simple integer mix-then-mod hash
static int hashKey(int v) {
    unsigned int u = (unsigned int)v;                 // 轉成 unsigned 避免負數取模未定義 / avoid UB with negative %
    u = ((u >> 16) ^ u) * 0x45d9f3bU;                 // 經典 bit-mix / well-known mixing constant
    u = ((u >> 16) ^ u);                              // 再混一次 / mix again
    return (int)(u % HASH_SIZE);                      // 落到桶範圍 / map into bucket range
}

// 找到 value 對應的桶；若沒有就建立一個空桶 / find-or-create the bucket for `value`
static Bucket* getBucket(Bucket **table, int value) {
    int h = hashKey(value);                           // 算雜湊位置 / compute bucket index
    for (Bucket *b = table[h]; b != NULL; b = b->next) {  // 走訪鏈結尋找 / walk the chain
        if (b->value == value) return b;              // 命中現有桶 / cache hit
    }
    Bucket *b = (Bucket*)malloc(sizeof(Bucket));      // 配置新桶 / allocate new bucket
    b->value = value;                                 // 設定鍵 / set key
    b->cap = 4;                                       // 初始容量 4 / start with capacity 4
    b->count = 0;                                     // 還沒有索引 / no indices yet
    b->idx = (int*)malloc(sizeof(int) * b->cap);      // 配置索引陣列 / allocate index array
    b->next = table[h];                               // 頭插法接到鏈結最前面 / prepend to chain
    table[h] = b;                                     // 更新桶頭 / update bucket head
    return b;                                         // 回傳桶 / return bucket
}

// 把索引 i 加進 value 桶；必要時擴容 / append index `i` to its bucket, grow if needed
static void bucketPush(Bucket *b, int i) {
    if (b->count == b->cap) {                         // 滿了要擴容 / grow on full
        b->cap *= 2;                                  // 加倍 / double capacity
        b->idx = (int*)realloc(b->idx, sizeof(int) * b->cap);  // realloc 重新配置 / realloc to new size
    }
    b->idx[b->count++] = i;                           // 寫入並前移計數 / write and bump count
}

// 把整張表釋放掉，避免記憶體洩漏 / free the whole hash table
static void freeTable(Bucket **table) {
    for (int h = 0; h < HASH_SIZE; h++) {             // 走過每個桶頭 / walk every bucket
        Bucket *b = table[h];
        while (b != NULL) {                           // 釋放鏈結中的每個節點 / free chain
            Bucket *next = b->next;
            free(b->idx);                             // 先釋放內部陣列 / free inner array
            free(b);                                  // 再釋放節點本身 / then the node
            b = next;
        }
    }
    free(table);                                      // 最後釋放桶頭陣列 / free the bucket array itself
}

int minJumps(int* arr, int arrSize) {
    if (arrSize <= 1) return 0;                       // 起點就是終點，0 步 / start == end already

    // 1) 預先建立 value -> 索引列表 的雜湊表
    //    Build the value -> indices map.
    Bucket **table = (Bucket**)calloc(HASH_SIZE, sizeof(Bucket*));  // 全部初始化為 NULL / zero-initialised
    for (int i = 0; i < arrSize; i++) {               // 掃一遍陣列 / one pass over arr
        Bucket *b = getBucket(table, arr[i]);         // 取得對應的桶 / fetch the bucket
        bucketPush(b, i);                             // 把索引塞進去 / append the index
    }

    // 2) BFS 所需的 visited 陣列與佇列
    //    visited[] and a ring-free queue for BFS.
    char *visited = (char*)calloc(arrSize, sizeof(char));  // 0=未訪 1=已訪 / 0=unseen, 1=seen
    int *queue = (int*)malloc(sizeof(int) * arrSize); // 佇列容量最多 n（每點最多入隊一次）/ at most n enqueues
    int qHead = 0, qTail = 0;                         // 佇列頭尾指標 / head/tail indices
    queue[qTail++] = 0;                               // 把起點入隊 / enqueue start
    visited[0] = 1;                                   // 標記為已訪 / mark visited
    int steps = 0;                                    // 目前的層數 / current BFS level

    int answer = -1;                                  // 預設 -1，理論上一定會更新 / default fallback

    // 3) 一次處理一整層 / process one full BFS level per outer iteration
    while (qHead < qTail) {                           // 佇列還有東西就繼續 / while queue not empty
        int levelSize = qTail - qHead;                // 這一層有多少節點 / nodes in this level
        for (int s = 0; s < levelSize; s++) {         // 把這一層全部彈出處理 / pop them all
            int i = queue[qHead++];                   // 取出當前索引 / dequeue index

            if (i == arrSize - 1) {                   // 抵達終點就回答 / reached last index
                answer = steps;
                goto done;                            // 跳出兩層迴圈做清理 / break out for cleanup
            }

            // 鄰居 1：i+1 / neighbour i+1
            if (i + 1 < arrSize && !visited[i + 1]) {
                visited[i + 1] = 1;                   // 標記避免重複入隊 / mark to avoid re-enqueue
                queue[qTail++] = i + 1;               // 入隊 / enqueue
            }
            // 鄰居 2：i-1 / neighbour i-1
            if (i - 1 >= 0 && !visited[i - 1]) {
                visited[i - 1] = 1;
                queue[qTail++] = i - 1;
            }
            // 鄰居 3：所有跟 arr[i] 同值的 j / all j with arr[j] == arr[i]
            Bucket *b = getBucket(table, arr[i]);     // 取出該值的桶 / fetch the value's bucket
            for (int k = 0; k < b->count; k++) {      // 一次處理整桶 / walk the whole bucket
                int j = b->idx[k];
                if (!visited[j]) {                    // 沒訪過才加入 / only enqueue unseen
                    visited[j] = 1;
                    queue[qTail++] = j;
                }
            }
            b->count = 0;                             // 關鍵：清空桶，避免下次再掃 / KEY: empty the bucket
        }
        steps++;                                      // 整層處理完，步數 +1 / finished this level
    }

done:
    free(visited);                                    // 釋放 visited / free visited
    free(queue);                                      // 釋放佇列 / free queue
    freeTable(table);                                 // 釋放整張雜湊表 / free hash table
    return answer;                                    // 回傳最少步數 / return answer
}