さまざまな大きさと色の 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つ作ることができる。

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

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

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