Problem 2: Cow Lineup [Brian Dean]
Фермер Джон нанял профессионального фотографа, чтобы сфотографировать некоторых из своих коров. Поскольку у него есть коровы разных пород, он хочет иметь фото как минимум одной коровы каждой породы.
N коров ФД выстроены в ряд (позиция каждой указывается x-координатой) и целочисленным номером породы. ФД планирует сделать фотографию непрерывного участка коров. Стоимость фотографии равна ее размеру – то есть разностью между максимальной и минимальной x-координатами коров, представленных на фотографии.
Помогите ФД вычислить минимальную стоимость фотографии, в которой находится по крайней мере одна корова каждой породы.
PROBLEM NAME: lineup
Формат входных данных
* Строка 1: количество коров, N (1 <= N <= 50,000).
* Строки 2..1+N: Каждая строка содержит два числа, разделенных одиночным пробелом, указывающих x-координату и номер породы одной коровы. Оба числа не превосходят миллиард.
Формат выходных данных
* Строка 1: Минимальную стоимость фотографии, содержащей не менее одной коровы каждой породы.
Примечание
Диапазон от x=22 до x=26 (длиной 4) содержит коровы всех пород (1,3,7).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
6
25 7
26 1
15 1
22 3
20 1
30 1
|
4
|