有一个无限的棋盘,分为多个单元格。单元格 $$$(x, y)$$$ 是第 $$$x_i$$$ 行和 $$$y_i$$$ 列的交集处的单元格。 $$$n$$$ 个黑色棋子被放置在棋盘上,第 $$$i$$$ 个黑色棋子占据单元格 $$$(x_i, y_i)$$$。
你想吃掉所有黑色棋子。为此,您可以执行以下操作:
- 将一个白色棋子放入任何空单元格中(可以选择具有整数坐标的任何单元格,只要它不包含任何棋子);
- 根据国际象棋规则用白棋之一走棋。
回想一下,当您在单元格 $$$(x, y)$$$ 中使用白棋移动时,国际象棋规则允许您选择以下操作之一:
- 如果单元格$$$(x + 1, y - 1)$$$中有一个黑色棋子,你可以捕获它——黑色棋子从棋盘上移除,白色棋子移动到$$$(x + 1, y - 1)$$$;
- 如果单元格$$$(x + 1, y + 1)$$$中有一个黑色棋子,你可以捕获它——黑色棋子从棋盘上移除,白色棋子移动到$$$(x + 1, y + 1)$$$;
- 如果单元格 $$$(x + 1, y)$$$ 为空,您可以将白色棋子移动到该单元格。
你可以执行任何有限的动作序列(放置白色棋子并移动它们)。你想要吃掉所有的黑棋子,并且可以证明这总是有可能的;并且你想要放置尽可能少的白色棋子。
要捕获所有 $$$n$$$ 黑色棋子,您必须放置最少数量的白色棋子?
输入
第一行包含一个整数 $$$n$$$ ($$$1 \le n \le 5 \cdot 10^5$$$) — 黑棋子的数量。
然后是 $$$n$$$ 行。第 $$$i$$$ 行包含两个整数 $$$x_i$$$ 和 $$$y_i$$$ ($$$1 \le x_i, y_i \le 5 \cdot 10^5$$$) 表示单元格 $$$(x_i, y_i)$$$ 中的一个黑色棋子。没有单元格被两个或更多黑色棋子占据。
输出
打印一个整数 — 为捕获所有 $$$n$$$ 黑色棋子而必须放置的白色棋子的最小数量。
示例
输入 #1
3 1 1 5 1 2 2
输出 #1
1
输入 #2
3 3 2 1 3 1 1
输出 #2
2
输入 #3
2 1 1 2 2
输出 #3
1