AT_oidashi_c 鏡餅

[problemUrl]: https://atcoder.jp/contests/oidashi/tasks/oidashi_c さまざまな大きさと色の $ n $ 個の餅が、塔のように積みあげられている。 上から $ t $ 番目の餅は、大きさが $ s_t $で、色が $ c_t $ である（ここでは、便宜上色は整数で表される）。 鏡餅は、3つの同じ色の餅を大きい順に下から重ねたものである。 あなたは、餅の塔から鏡餅を作るために以下の操作を行う。 餅の塔の上から餅を1つづつ取り、受け取るか捨てるかのどちらかを行う。 **3つ受け取るごと**に、受け取った餅を順番に重ねて鏡餅を作る。 つまり、$ i,j,k $番目($ i\ )の餅をこの順に \ 受け取ったとき、 \ 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 $ 作ることのできる鏡餅の個数の最大を出力せよ。出力の末尾には改行を入れること。 ``` 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 ```

N/A

N/A