48. Оценка разнообразия

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

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

Дана выборка товаров из разных категорий: $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_{id}$ - порядок товаров в списке.

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

Числа в строках разделены одиночными пробелами.

Выведите одно число, равное значению вычисленного разнообразия списка товаров.