47. Разнообразие товаров

Выдача бывает полезной, бывает информативной, а бывает разнообразной.

Разработайте алгоритм, который будет упорядочивать товары наиболее разнообразно.

Дана выборка товаров из разных категорий: $product_{i}$, $category_{i}$ - идентификатор продукта и его категория.

Расположите объекты в таком порядке, чтобы минимальная разность позиций между товарами одной категории была как можно больше.

Если все товары различных категорий, то расположите их в произвольном порядке.

В первой строке записано одно целое число $n$ ($1 \le n \le 100\,000$) - количество товаров в списке.

Далее в каждой из $n$ строк через пробел записано по два целых числа $product_{i}$ и $category_{i}$ ($0 \le product_{i}, category_{i} \le 2^{30}$) - id продукта и его категория.

Гарантируется, что все величины $product_{i}$ различны.

Выведите $n$ целых чисел $product_{i}$ - некоторая перестановка величин.

Для результирующего порядка значение наименьшего расстояния между товарами одной категории должно быть максимальным возможным.

Если подходящих перестановок товаров несколько, выведите любую из них.