Hungry Queen 2#3457
Hungry queen is standing at the cell of an infinite chessboard. There are also pawns on the chessboard, numbered from to ; the -th pawn is located at the cell (x_i, y_i).
The queen is going to take as many pawns as possible. She's going to take pawns in the order they are numbered: pawn , pawn , etc. All her moves must follow chess queen's rules — the queen can move only horizontally, vertically, or diagonally. The queen must capture a pawn with each move. She is not allowed to jump over pawns. Captured pawns are removed from the board. The pawns don't move.
Help the queen to find the maximal number of successive pawns she can take.
The first line of the input file contains — the number of pawns (1 \leq n \leq 100000). The following lines contain the coordinates of the pawns (the coordinates do not exceed 10^9 in their absolute values).
No pawn is located at the cell . No two pawns occupy the same cell.
Output one number — the number of successive pawns the queen can take.
Example 1