This page is still under construction.

Parts of this page are still being built. What you see may change.

Comfortable Cows

Interview

Time limit1sMemory limit512 MB

Summary
Cows arrive one at a time on a grid; after each arrival, report how many cows have exactly three occupied orthogonal neighbors.
Level

Medium6 of 10

Topics
Implementation, Hash map, Simulation, Array
Solved
No attempts yet

Problem

Farmer John's pasture can be regarded as a large 2D grid of square "cells" (picture a huge chessboard). Initially, the pasture is empty.

Farmer John will add NN (1≤N≤1051\le N\le 10^5) cows to the pasture one by one. The iith cow will occupy a cell (xi,yi)(x_i,y_i) that is distinct from the cells occupied by all other cows (0≤xi,yi≤10000\le x_i,y_i\le 1000).

A cow is said to be "comfortable" if it is horizontally or vertically adjacent to exactly three other cows. Farmer John is interested in counting the comfortable cows on his farm. For each ii in the range 1…N1 \ldots N, output the total number of comfortable cows after the iith cow is added to the pasture.

Input

The first line contains a single integer NN. Each of the next NN lines contains two space-separated integers, indicating the (x,y)(x,y) coordinates of a cow's cell. It is guaranteed that all these cells are distinct.

Output

The iith line of output should contain the total number of comfortable cows after the first ii cows are added to the pasture.

Examples1

  1. Example 1

    Input
    8
0 1
1 0
1 1
1 2
2 1
2 2
3 1
3 2
    Expected output
    0
0
0
1
0
0
1
2