// 解法一 
    // 暴力双重循环
    class Solution {
    public:
        int maxDistance(vector<int>& colors) {
            int n = colors.size();
            int ans = 1;
            for (int i = 0; i < n; i++) {
                for (int j = i + 1; j < n; j++) {
                    if (colors[j] != colors[i]) {
                        ans = max(ans, j - i);
                    }
                }
            }
            return ans;
        }
    };
    
    // 解法二
    // 最优解的一端一定在边界上，假如不在边界上
    // si si si [si] .... [sj] sj sj sj
    class Solution {
    public:
        int maxDistance(vector<int>& colors) {
            int n = colors.size();
            int left = 0;
            int right = n - 1;
            while (right >= 0 && colors[right] == colors.front()) {
                right--;
            }
            while (left < n && colors[left] == colors.back()) {
                left++;
            }
            return max(right, n - left - 1);
        }
    };

    // 暴力模拟，没什么好说的
    class Solution {
    public:
        int wateringPlants(vector<int>& plants, int capacity) {
            int n = plants.size();
            
            int ans = 0;
            int cur = 0;
            int tmpCap = capacity;
            for (int i = 0; i < n; i++) {
                if (tmpCap - plants[i] < 0) {
                    //cout << "cur " << i << endl;
                    ans += cur * 2;
                    tmpCap = capacity;
                }
                cur++;
                ans++;
                tmpCap -= plants[i];
            }
            
            return ans;
        }
    };

   // 哈希记录 value -- value在数组中的位置的集合
    // 查询时二分查找区间左右包含的数字，O(nlogn)
    // ps: 老是忘记lower_bound和upper_bound的区别-_-
    // lower_bound: 二分查找第一个大于或等于num的数字
    // upper_bound: 查找第一个大于num的数字
    class RangeFreqQuery {
    public:
        RangeFreqQuery(vector<int>& arr) {
            for (int i = 0; i < arr.size(); i++) {
                mp[arr[i]].push_back(i);
            }
        }
        
        int query(int left, int right, int value) {
            if (mp.count(value) == 0) {
                return 0;
            }
            auto& item = mp[value];
            int first = upper_bound(item.begin(), item.end(), left - 1) - item.begin();
            int last = upper_bound(item.begin(), item.end(), right) - item.begin();
            //cout << last << " - " << first << endl;
    
            return last - first;
        }
        
        unordered_map<int, vector<int>> mp;
    };

   // 要求是十进制和k进制都是镜像数字
    // 这次感觉是被题吓住了。。。以为会后什么奇妙的算法，还是把朴素的思路写出来再去优化
    class Solution {
    public:
        long long kMirror(int k, int n) {
            // 检验是否为k进制镜像数
            auto Check = [](LL num, int k) -> bool {
                string str;
                while (num) {
                    str.push_back(num % k + '0');
                    num /= k;
                }
                for (int i = 0, j = str.length() - 1; i < j; i++, j--) {
                    if (str[i] != str[j]) {
                        return false;
                    }
                }
                return true;
            };
    
            LL ans = 0;
            // 构造镜像十进制数后检查是否为k进制数
            for (int len = 1; ;len++) {
                int l = pow(10, len - 1);
                int r = pow(10, len);
    
                for (int i = l; i < r; i++) {
                    LL a = i, b = i / 10;
                    while (b) {
                        a = a * 10 + b % 10;
                        b /= 10;
                    }
                    if (check(a, k)) {
                        ans += a;
                        if (--n == 0) {
                            return ans;
                        }
                    }
                }
    
                for (int i = l; i < r; i++) {
                    LL a = i, b = i;
                    while (b) {
                        a = a * 10 + b % 10;
                        b /= 10;
                    }
                    if (check(a, k)) {
                        ans += a;
                        if (--n == 0) {
                            return ans;
                        }
                    }
                }
            }
            return ans;
        }
    };