Hungry Queen 2
Hungry queen is standing at the cell (0, 0) of an infinite chessboard. There are also n pawns on the chessboard, numbered from 1 to n, the i-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 take pawns in order they are numbered: pawn 1, pawn 2, etc. All her moves must follow chess queens rules - the queen can move only horizontally, vertically and diagonally. She is not allowed to jump over pawns. The pawns don't move.
Help the queen to find the maximal number of successive pawns she can take.
Input
The first line of the input file contains n - the number of pawns (1 ≤ n ≤ 100000). The following n lines contain coordinates of pawns (coordinates do not exceed 10^9 by their absolute values).
No pawn is located at the cell (0, 0). No two pawns occupy the same cell.
Output
Output one number - the number of successive pawns the queen can take.