M. Фотография стада

В ряд выстроены $n$ коров, у каждой известны координата и номер породы. Фотограф снимает непрерывный по координате участок; стоимость фотографии равна разности между наибольшей и наименьшей координатой попавших в кадр коров.

Найдите наименьшую стоимость фотографии, на которой есть хотя бы одна корова каждой породы.

В первой строке $n$ от $1$ до $10^5$. В следующих $n$ строках — координата и номер породы, оба от $1$ до $10^9$. Координаты различны.

Одно число.