Solution
Intuition\n Describe your first thoughts on how to solve this problem. \n\nThe segment tree is based on Boyer-Moore majority algorithm: https://en.wikipedia.org
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\n\nThe segment tree is based on Boyer-Moore majority algorithm: https://en.wikipedia.org/wiki/Boyer%E2%80%93Moore_majority_vote_algorithm\n\nIn particular the underlying array of the segment tree is a pair of (element, count) returned by the Boyer-Moore algorithm. Here the element is the potential majority element of the array (if it exists) and the count is the positive count for the element that survives the algorithm (not the actual frequency in the array).\n\nThe segment tree merge works as follows:\n\n```\n    if (a.element == b.element)\n    {\n        return {a.element, a.count + b.count};\n    }\n    else if (a.element > b.element)\n    {\n        return {a.element, a.count - b.count};\n    }\n    else\n    {\n        return {b.element, b.count - a.count};\n    }\n```\n\nThis is because we can consider this merge as simply merging a combination of the surviving elements from both smaller merges - because the outcome of Boyer-Moore is independent of the order of the elements, we can always arrange the elements in such a way that all other elements wipe out all except a.count of a.element and b.count of b.element, and these copies of a.element and b.element are placed consecutively at the end.\n\nHowever, the element returned is only the potential majority, we also have to check if it is actually the majority element, we can do this by storing a mapping of value to the indices it appears in.\n\nThen we can binary search this range of indices for the element returned from the segment tree for the left and right indices of the query, to find the count of elements in this range, and compare it with the given threshold.\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\n\n# Complexity\n- Time complexity:\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity:\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```\nstruct SegTree\n{\n    vector<vector<int>> t;\n\n    SegTree(int n)\n    {\n        t.assign(2*n, vector<int>(2, 0));\n    }\n\n    void insert(int i, int l, int r, int pos, int val)\n    {\n        if(pos < l || pos > r || l > r)\n        {\n            return;\n        }\n\n        if(l == r)\n        {\n            t[i] = {val, 1};\n            return;\n        }\n\n        int mid = l + (r-l)/2;\n        insert(i+1, l, mid, pos, val);\n        insert(i+2*(mid-l+1), mid+1, r, pos, val);\n        t[i] = merge(t[i+1], t[i+2*(mid-l+1)]);\n    }\n\n    vector<int> query(int i, int l, int r, int lq, int rq)\n    {\n        if(rq < l || r < lq)\n        {\n            return {0, 0};\n        }\n\n        if(lq <= l && r <= rq)\n        {\n            return t[i];\n        }\n\n        int mid = l + (r-l)/2;\n        vector<int> left = query(i+1, l, mid, lq, rq);\n        vector<int> right = query(i+2*(mid-l+1), mid+1, r, lq, rq);\n        return merge(left, right);\n    }\n\n    vector<int> merge(vector<int>& t1, vector<int>& t2)\n    {\n        if(t1[0] == t2[0])\n        {\n            return {t1[0], t1[1] + t2[1]};\n        }\n        else if(t1[1] > t2[1])\n        {\n            return {t1[0], t1[1] - t2[1]};\n        }\n        else\n        {\n            return {t2[0], t2[1] - t1[1]};\n        }\n    }\n};\n\n\nclass MajorityChecker {\npublic:\n    SegTree st;\n    vector<int> a;\n    int n;\n    unordered_map<int,vector<int>> mp;\n\n    MajorityChecker(vector<int>& arr) : st(arr.size()) {\n        this->n = arr.size();\n        this->a = arr;\n        mp.clear();\n        \n        for(int i = 0; i<arr.size(); i++)\n        {\n            st.insert(0, 0, n-1, i, arr[i]);\n            mp[arr[i]].push_back(i);\n        }\n    }\n    \n    int query(int left, int right, int threshold) {\n        vector<int> ans = st.query(0, 0, n-1, left, right);\n\n        int lo = 0;\n        int hi = (int)mp[ans[0]].size() - 1;\n        int ans1 = -1;\n\n        // find the first element >= left\n        while(lo <= hi)\n        {\n            int mid = lo + (hi - lo)/2;\n            if(mp[ans[0]][mid] >= left)\n            {\n                ans1 = mid;\n                hi = mid-1;\n            }\n            else\n            {\n                lo = mid+1;\n            }\n        }\n\n        if(ans1 == -1)\n        {\n            return -1;\n        }\n\n        lo = 0;\n        hi = (int)mp[ans[0]].size() - 1;\n        int ans2 = -1;\n\n        // find the last element <= right\n        while(lo <= hi)\n        {\n            int mid = lo + (hi - lo)/2;\n            if(mp[ans[0]][mid] <= right)\n            {\n                ans2 = mid;\n                lo = mid+1; \n            }\n            else\n            {\n                hi = mid-1;\n            }\n        }\n\n        if(ans2 == -1)\n        {\n            return -1;\n        }\n\n        return ans2 - ans1 + 1 >= threshold ? ans[0] : -1;\n    }\n};\n\n/**\n * Your MajorityChecker object will be instantiated and called as such:\n * MajorityChecker* obj = new MajorityChecker(arr);\n * int param_1 = obj->query(left,right,threshold);\n */\n```
['C++']