C - 鏡餅

Time Limit: 2 sec / Memory Limit: 298 MB

問題文

さまざまな大きさと色の n 個の餅が、塔のように積みあげられている。 上から t 番目の餅は、大きさが s_tで、色が c_t である(ここでは、便宜上色は整数で表される)。

鏡餅は、3つの同じ色の餅を大きい順に下から重ねたものである。 あなたは、餅の塔から鏡餅を作るために以下の操作を行う。 餅の塔の上から餅を1つづつ取り、受け取るか捨てるかのどちらかを行う。 3つ受け取るごとに、受け取った餅を順番に重ねて鏡餅を作る。 つまり、i,j,k番目(i < j < k)の餅をこの順に 受け取ったとき、 s_i > s_j > s_k かつ c_i = c_j = c_k であるなら、またその時に限って、鏡餅を1つ作ることができる。

餅の塔の情報が与えられる。最大でいくつの鏡餅をつくることができるか求めよ。


入力

入力は以下の形式で標準入力から与えられる。
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

鏡餅を2つ作るには、たとえば以下のようにすればよい。 1,3,4番目の餅を受け取り、大きさ9,8,7で色1の鏡餅をひとつ作る。 5,7,8番目の餅を受け取り、大きさ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