C# Random + BinarySearch
csharp\npublic class MajorityChecker\n{\n    const int ProbeCount = 20;\n\n    int[] arr;\n    Dictionary<int, List<int>> positions;\n\n    public MajorityCheck
```csharp\npublic class MajorityChecker\n{\n    const int ProbeCount = 20;\n\n    int[] arr;\n    Dictionary<int, List<int>> positions;\n\n    public MajorityChecker(int[] arr)\n    {\n        this.arr = arr;\n        this.positions = new();\n\n        for (var i = 0; i < arr.Length; i++)\n        {\n            if (!positions.TryGetValue(arr[i], out var indices))\n                positions[arr[i]] = indices = new();\n\n            indices.Add(i);\n        }\n    }\n\n    public int Query(int left, int right, int threshold)\n    {\n        for (var probe = 0; probe < ProbeCount; probe++)\n        {\n            var i = Random.Shared.Next(left, right);\n            var indices = positions[arr[i]];\n\n            if (indices.Count >= threshold)\n            {\n                var start = indices.BinarySearch(left);\n                var end = indices.BinarySearch(right);\n                start = start < 0 ? ~start : start;\n                end = Math.Abs(end + 1);\n\n                if (end - start >= threshold)\n                    return arr[i];\n            }\n        }\n\n        return -1;\n    }\n}\n```
['Binary Search', 'C#']