C - 鏡餅
解説
/
入力は以下の形式で標準入力から与えられる。
作ることのできる鏡餅の個数の最大を出力せよ。出力の末尾には改行を入れること。
実行時間制限: 2 sec / メモリ制限: 291 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_ns_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