Find an element appearing more than times in , or report none exists. Observation: If a majority exists, it's either: - The median (quantile query) - Or we can verify a candidate in Algorithm: Find median using kthSmallest
Count its frequency
If frequency , return it
Otherwise, no majority exists Time: for single query. This works because the majority element, if it exists, must be the median.