← 返回题目列表

AtCoder · oidashi_c

C. 加贺美糬

中文机器翻译题面 查看原题

問題文

各种尺寸和颜色 n 麻糬像塔一样堆积起来。 从上面 t 麻糬的大小是 s_t颜色是 c_t (这里,为了方便起见,颜色以整数表示)。

加贺美麻糬是由三个相同颜色的麻糬按照大小从下到上的顺序堆叠而成。 您执行以下操作以从麻糬塔制作镜麻糬。 从麻糬塔顶取出一张麻糬,要么接受,要么扔掉。 每次您收到 3将收到的麻糬堆叠起来,制作镜麻糬。 换句话说,i,j,k番目(i < j < k) 麻糬按此顺序 当你收到它时, s_i > s_j > s_k 和 c_i = c_j = c_k 当且仅此,你才能制作一张镜麻糬。

给出了有关麻糬塔的信息。找出你能制作的镜麻糬的最大数量。


入力

输入是按以下格式从标准输入给出的。
n
s_1 c_1
... 
s_n c_n
s_t,c_t 是 每个从上面 代表第 t 个麻糬的大小和颜色 ( 1 \leq t \leq n )。 两者都表示为整数。
  • n,s_i,c_i 是一个整数
  • 1 \leq n \leq 10^5
  • 1 \leq s_i \leq 10^9
  • 1 \leq c_i \leq 10^5

出力

打印可以制作的镜饼的最大数量。在输出末尾添加换行符。

入力例 1

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

出力例 1

2

例如,要制作两个 kagami mochi,请执行以下操作。 取第 1、3、4 个麻糬,制作 1 个尺寸为 9、8、7、颜色为 1 的镜麻糬。 取第 5、7、8 个麻糬,制作 1 个尺寸为 5、4、3、颜色为 2 的镜麻糬。


入力例 2

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

出力例 2

0

您不能使用不同颜色的麻糬来制作镜麻糬。 它的编号为


入力例 3

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

出力例 3

1