Комфортные коровы (Бронза)
Комфортные коровы (Бронза)
Пастбище Фермера Джона может быть представлено как огромная 2D-решётка ячеек (огромная шахматная доска). Изначально пастбище пустое.
ФД добавит n коров на пастбище одну за одной. i-ая корова занимает ячейку (xi
, yi
), которая отличается от ячеек, занятых всеми другими коровами.
Говорят, что корове "комфортабельно", если соседями по горизонтали и вертикали она имеет ровно три других коровы. ФД хочет посчитать, скольким коровам комфортабельно на его пастбище. Для каждого i в интервале 1..n, выведите общее количество коров, которым комфортабельно после того, как i-ая корова добавлена на пастбище.
Входные данные
Первая строка содержит одно целое число n (1 ≤ n ≤ 105
). Каждая из последующих n строк содержит два целых числа, указывающих (x, y) (0 ≤ x, y ≤ 1000) - координаты ячейки коровы. Гарантируется, что все ячейки различны.
Выходные данные
Выведите в i-ой строке общее количество коров, которым комфортабельно после добавления i-ой коровы на пастбище.
Пример
После того, как добавлены первые 4 коровы, корове в ячейке (1, 1) стало комфортабельно.
После того, как добавлены первые 7 коров, корове в ячейке (2, 1) стало комфортабельно.
После того, как добавлены первые 8 коров, корове в ячейках (2, 1) и (2, 2) стало комфортабельно.
8 0 1 1 0 1 1 1 2 2 1 2 2 3 1 3 2
0 0 0 1 0 0 1 2