= Solution
For an integer pivot $0\leq p\leq N+1$, exactly $k$ entries lie in $[0,p)$. That interval contains $p$ possible <integers>. If $k<p$, the <pigeonhole principle> implies that \b[some value in $[0,p)$ is missing]. Counting occurrences rather than distinct entries only strengthens this argument: $k$ occurrences cannot cover more than $k$ distinct values.
For completeness, if $p>N+1$ the lower side contains the entire permitted value range, which already has a missing value. If $p\leq0$, the condition $k<p$ is impossible. Thus the general conclusion is a missing permitted value below $p$; an internal pivot gives useful localization.
Back to article page
