Count distinct values in a sorted array with few distinct values

A sorted array is huge but holds only a handful of distinct values. Count the distinct values faster than scanning every element: from each new value, binary search (or gallop) to where it ends, so the cost depends on the number of distinct values rather than the length. Start with the linear scan, then optimize.