[ABC053D] Card Eater

题意翻译

有一堆牌,每张牌上有一个数字。 每次可以取出其中3张,丢掉数字最大的和数字最小的牌,把中间那张再放回牌堆。 要求最后所有剩余牌上的数字互不相同,求最多能剩几张牌。

题目描述

[problemUrl]: https://atcoder.jp/contests/abc053/tasks/arc068_b すぬけくんはカードゲームで遊ぶことにしました。 $ N $ 枚からなるカードの山があり、上から $ i $ 枚目のカードには整数 $ A_i $ が書かれています。 すぬけくんはこのカードの山に対し $ 0 $ 回以上、以下の操作を行い、残ったカードに書かれた値が互いに異なるようにしたいです。最大で何枚のカードを残すことが可能か求めなさい。なお、$ N $ は奇数であり、少なくとも $ 1 $ 枚のカードを残すことが可能であることが保証されます。 操作:カードの山から任意の $ 3 $ 枚のカードを抜き出す。抜き出したカードのうち書かれた値が最大であるようなカード $ 1 $ 枚と最小であるようなカード $ 1 $ 枚の合計 $ 2 $ 枚を選んで食べる。その後残った $ 1 $ 枚をカードの山に戻す。

输入输出格式

输入格式


入力は以下の形式で標準入力から与えられる。 > $ N $ $ A_1 $ $ A_2 $ $ A_3 $ ... $ A_{N} $

输出格式


答えを出力せよ。

输入输出样例

输入样例 #1

5
1 2 1 3 7

输出样例 #1

3

输入样例 #2

15
1 3 5 2 1 3 2 8 8 6 2 6 11 1 1

输出样例 #2

7

说明

### 制約 - $ 3\ ≦\ N\ ≦\ 10^{5} $ - $ N $ は奇数 - $ 1\ ≦\ A_i\ ≦\ 10^{5} $ - $ A_i $ は整数 ### Sample Explanation 1 操作を $ 1 $ 回行って $ 1,1,2 $ を取り出すというのが最適な操作手順の $ 1 $ つです。最大値である $ 2 $ と書かれたカードで最小値である $ 1 $ と書かれたカードがそれぞれ $ 1 $ 枚ずつ食べられ、残った $ 1 $ と書かれたカードがカードの山に戻されます。カードの山に残っているカードは $ 1,3,7 $ となり、これらは互いに異なります。