Комфортні корови (Срібло)
Пасовище фермера Нхой можна уявити як величезну двовимірну решітку клітинок, схожу на шахову дошку. Спочатку пасовище порожнє.
Фермер Нхой планує додати 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).