题目描述

Buguré 新城区共有 $N$ 套可购买的住宅。第 $i$ 套住宅位于坐标 $(X_i,Y_i)$。

定义两套住宅之间的曼哈顿距离为

$$\operatorname{dist}(i,j)=|X_i-X_j|+|Y_i-Y_j|.$$

再定义

$$d(i)=\min_{j\ne i}\operatorname{dist}(i,j),$$

即第 $i$ 套住宅到最近的另一套住宅的距离。

Àles、RANDy 和 Țeba 是三位从小一起长大的好朋友，他们每人想购买一套住宅。记三人购买的住宅编号分别为 $A,R,T$，要求满足：

1. $A<R<T$；
2. $\operatorname{dist}(A,R)=\operatorname{dist}(R,T)=\operatorname{dist}(A,T)$；
3. $d(A)=d(R)=d(T)=\operatorname{dist}(A,R)$。

请计算有多少个三元组 $(A,R,T)$ 满足以上条件。

输入格式

第一行输入一个整数 $N$。

接下来 $N$ 行，每行输入两个整数 $X_i,Y_i$，表示第 $i$ 套住宅的坐标。

输出格式

输出一个整数 $S$，表示满足条件的三元组数量。

数据范围与约束

• $1\le N\le 250000$；
• $0\le X_i,Y_i\le 10^9$；
• 不存在两套住宅坐标完全相同。

子任务

子任务	分值	限制
1	7	$N\le 100$
2	14	$N\le 2000$
3	28	对所有 $i$，$X_i,Y_i\le 2000$
4	51	无额外限制

样例

输入

5
1 1
3 1
2 2
2 6
4 4

输出

1

样例解释

唯一满足条件的三元组是 $(1,2,3)$。

三元组 $(3,4,5)$ 虽然满足

$$\operatorname{dist}(3,4)=\operatorname{dist}(4,5)=\operatorname{dist}(3,5),$$

但 $d(3)=2$，$d(4)=4$，$d(5)=4$，不满足第三个条件。