Cow Lineup

A farmer wants a single photograph that includes at least one cow of every distinct breed present in the herd.

The $N$ cows stand at various positions along a line. Each cow is described by an integer position (its $x$ coordinate) and an integer breed ID. The photograph captures a contiguous range of cows along the line, and its cost equals its size — the difference between the maximum and minimum $x$ coordinates of the cows inside that range.

Compute the minimum possible cost of a photograph that contains at least one cow of every distinct breed present in the herd.

• Line 1: an integer $N$ ($1 \le N \le 50{,}000$), the number of cows.
• Lines 2 to $N+1$: each line contains two space-separated positive integers, the $x$ coordinate and the breed ID of one cow. Both values are at most $1{,}000{,}000{,}000$.

• A single line with the smallest cost of a photograph that contains at least one cow of every distinct breed ID.

Suppose there are $6$ cows at positions $25, 26, 15, 22, 20, 30$ with breed IDs $7, 1, 1, 3, 1, 1$ respectively. The distinct breeds are $1$, $3$, and $7$. The range from $x = 22$ up to $x = 26$ has size $4$ and contains all three distinct breeds, which is the minimum possible cost.