Пастбище Фермера Нхой может рассматриваться как огромная 2D-решётка ячеек (шахматная доска). Изначально пастбище пустое.
ФН добавит n коров на пастбище одну за другой. i-ая корова займёт ячейку (x[i]
, y[i]
), которая отличаетсяот ячеек, занятых всеми другими коровами.
Корова называется "комфортабельной", если она имеет ровно трёх соседей по горизонтали и вертикали. Комфортабельные коровы дают меньше молока, поэтому ФН хочет добавлять коров пока нет комфортабельных (включая ту которую он добавит). Заметим, что добавляемые коровы не обязательно должны иметь координаты x и y в интервале 0..1000.
Для каждого i в интервале 1..n, выведите минимальное количество коров, которое он должен добавить, чтобы не осталось комфортабельных коров, если считать, что на пастбище находятся только коровы 1..i.
Первая строка содержит целое число n (1 ≤ n ≤ 10^5
). Каждая из следующих n строк содержит по 2 целых числа, указывающих (x, y) (0 ≤ x, y ≤ 1000) координаты ячейки с коровой.
Выведите минимальное количество коров, которое ФН должен добавить, для каждого i в интервале 1..n, на отдельной строке.
Для i = 4, ФН должен добавить корову в позицию (2, 1), чтобы сделать корову в позиции (1, 1) некомфортабельной.
Для i = 9, лучшее что ФН может сделать - добавить коров в позиции (2, 0), (3, 0), (2, −1), (2, 3).