// Algorithm: BFS over array indices. Edges go to i-1, i+1, and every j with arr[i]==arr[j].
// Pre-build unordered_map<value, vector<int>>; after expanding any index of value v,
// clear that bucket so duplicate-value inputs don't blow up to O(n^2).

#include <vector>           // std::vector：動態陣列容器 / dynamic array
#include <queue>            // std::queue：FIFO 佇列 / FIFO queue
#include <unordered_map>    // 雜湊表，平均 O(1) 查詢 / hash map, O(1) average lookup

class Solution {
public:
    int minJumps(std::vector<int>& arr) {
        int n = (int)arr.size();                          // 取得長度 / array length
        if (n <= 1) return 0;                             // 起點就是終點 / start == end

        // value -> 該值所有出現位置 / value -> all indices where it occurs
        // unordered_map 用雜湊，平均 O(1) / unordered_map is a hash map
        std::unordered_map<int, std::vector<int>> sameVal;
        sameVal.reserve(n * 2);                           // 預留空間減少 rehash / pre-reserve to avoid rehashing
        for (int i = 0; i < n; ++i) {                     // 預處理：一次掃過 / single pass
            sameVal[arr[i]].push_back(i);                 // 把 i 加到對應的列表 / append i to its bucket
        }

        std::vector<char> visited(n, 0);                  // 用 char 當布林省空間 / use char as bool to save space
        std::queue<int> q;                                // BFS 佇列 / BFS queue
        q.push(0);                                        // 從索引 0 出發 / start from index 0
        visited[0] = 1;                                   // 標記為已訪 / mark visited
        int steps = 0;                                    // 當前層數 = 已走步數 / level == steps taken

        while (!q.empty()) {                              // 佇列空了就結束 / loop until empty
            int levelSize = (int)q.size();                // 這一層的節點數 / freeze the level boundary
            for (int s = 0; s < levelSize; ++s) {         // 處理整層 / process one full level
                int i = q.front();                        // 取出隊頭 / peek front
                q.pop();                                  // 彈出 / pop

                if (i == n - 1) return steps;             // 抵達終點 / reached the target

                // 鄰居 i+1 / right neighbour
                if (i + 1 < n && !visited[i + 1]) {
                    visited[i + 1] = 1;
                    q.push(i + 1);
                }
                // 鄰居 i-1 / left neighbour
                if (i - 1 >= 0 && !visited[i - 1]) {
                    visited[i - 1] = 1;
                    q.push(i - 1);
                }
                // 同值索引：用 auto& 取引用，避免複製整個 vector / take a reference, no copy
                auto& bucket = sameVal[arr[i]];
                for (int j : bucket) {                    // range-for：遍歷容器的語法糖 / range-based for loop
                    if (!visited[j]) {
                        visited[j] = 1;
                        q.push(j);
                    }
                }
                bucket.clear();                           // 關鍵剪枝：清空避免 O(n^2) / KEY pruning step
            }
            ++steps;                                      // 整層處理完才加一 / increment after finishing the level
        }
        return -1;                                        // 題目保證可達，理論不會到這 / unreachable per constraints
    }
};