AT_oidashi_c.鏡餅

在一个塔形结构中，堆积了 $n$ 个不同大小和颜色的饼。从上到下，第 $t$ 个饼的大小为 $s_t$，颜色为 $c_t$（使用整数表示）。

镜饼是由三个大小递减且颜色相同的饼组成的。要制作镜饼，需要从饼塔顶端开始依次取出饼，并选择是接收还是丢弃。每当接收三个饼后，如果接收的这三个饼满足 $s_i > s_j > s_k$ 且 $c_i = c_j = c_k$，就可以按顺序制作一个镜饼。

给定饼塔的信息，求最多能制作多少个镜饼。

输入格式

标准输入包含：

第一行是整数 $n$，表示饼的总数。接下来的 $n$ 行，每行两个整数 $s_t$ 和 $c_t$，表示第 $t$ 个饼的大小和颜色。

输出格式

输出一个整数，即最多能制作的镜饼数量，输出末尾要有换行符。

数据范围与提示

• $1 \leq n \leq 10^5$
• $1 \leq s_i \leq 10^9$
• $1 \leq c_i \leq 10^5$

示例

输入

8
9 1
6 1
8 1
7 1
5 2
2 1
4 2
3 2

输出

2

在该示例中，可以通过接收第1、3、4号饼，制作一个大小为9、8、7且颜色为1的镜饼；接收第5、7、8号饼，制作一个大小为5、4、3且颜色为2的镜饼，总共可以制作两个镜饼。

输入

9
9 1
8 2
7 3
6 4
5 5
4 6
3 7
2 8
1 1

输出

0

在该示例中，由于颜色不同，无法制作镜饼。

输入

12
72846 3
36153 3
35490 4
825561 1
21513 3
24495 1
13460 2
8 2
358 1
466 4
6287 3
98738 4

输出

1

本翻译由 AI 自动生成