L. Limited Rooks
time limit per test
2 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output

You are given an infinite chessboard with $$$N$$$ obstacles placed on it. We call a rook is limited if it can move to only a finite number of squares. Your task is to count how many empty squares on the board will result in a limited rook if you place one there. Note that you cannot place a rook on a square that occupied by an obstacle.

A rook moves any number of squares in the same row or column, but cannot move to or jump over the obstacles. More precisely, a rook placed at square $$$(r, c)$$$ can move to a square $$$(r', c')$$$ only if one of the conditions is satisfied:

  • $$$r' = r$$$, $$$c' \gt c$$$ and all squares $$$(r, y)$$$ with $$$c \lt y \leq c'$$$ contain no obstacles.
  • $$$r' = r$$$, $$$c' \lt c$$$ and all squares $$$(r, y)$$$ with $$$c' \leq y \lt c$$$ contain no obstacles.
  • $$$c' = c$$$, $$$r' \gt r$$$ and all squares $$$(x, c)$$$ with $$$r \lt x \leq r'$$$ contain no obstacles.
  • $$$c' = c$$$, $$$r' \lt r$$$ and all squares $$$(x, c)$$$ with $$$r' \leq x \lt r$$$ contain no obstacles.
Input

The first line of the input contains an integer $$$N$$$, the number of obstacles.

Each of the next $$$N$$$ line contains two integers $$$r_i, c_i$$$, indicating that the $$$i$$$-th obstacle is placed at $$$(r_i, c_i)$$$.

  • $$$1 \leq N \leq 5 \cdot 10^5$$$
  • $$$0 \leq r_i, c_i \leq 10^9$$$
  • No two obstacles share the same square.
Output

Output a single line with one integer represents the number of squares on the board will result in a limited rook if you place one there.

Examples
Input
6
1 0
1 5
0 1
0 2
48763 2
56562 1
Output
2
Input
15
3 5
4 1
5 4
0 5
1 2
0 4
2 0
4 5
3 3
2 3
0 2
0 3
0 1
1 1
3 2
Output
4