Cow Lineup

Time limit1sMemory limit128 MB

Summary

Find the minimum span of x coordinates covering at least one cow of every distinct breed id.

Level: Medium6 of 10
Topics: Sorting, Sliding window, Hash map, Two pointers
Solved: No attempts yet

Problem

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.

Input

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$ .

Output

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

Hint

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.

Examples3

Example 1
Input
```
6
25 7
26 1
15 1
22 3
20 1
30 1
```
Expected output
```
4
```
Example 2
Input
```
1
5 3
```
Expected output
```
0
```
Example 3
Input
```
4
1 5
100 5
50 5
7 5
```
Expected output
```
0
```