AT_joi2026_yo2_b 究極の団子職人 (Ultimate Dango Maker)

JOI 君は団子職人である．団子には色 $ 1 $ から色 $ N $ までの $ N $ 色あり，JOI 君は色 $ i $ ( $ 1 \leqq i \leqq N $ ) の団子を $ A_i $ 個持っている． JOI 君は持っている団子から $ 3 $ 個選んで $ 1 $ 本の**串団子**を作ることができる．ただし，選んだ $ 3 $ 個の団子の色が $ c_1, c_2, c_3 $ ( $ 1 \leqq c_1 \leqq N $ ， $ 1 \leqq c_2 \leqq N $ ， $ 1 \leqq c_3 \leqq N $ ) であるとき， $ c_1 $ と $ c_2 $ ， $ c_2 $ と $ c_3 $ ， $ c_3 $ と $ c_1 $ の差はそれぞれ $ 1 $ 以下でなければならない．つまり以下の条件がすべて成り立つ必要がある． - $ |c_1 - c_2| \leqq 1 $ - $ |c_2 - c_3| \leqq 1 $ - $ |c_3 - c_1| \leqq 1 $ 複数の串団子で同じ団子を共有して使うことはできない．JOI 君は持っている団子をうまく選んでできるだけ多くの串団子を作りたい． JOI 君が持っている団子についての情報が与えられたとき，JOI 君が作ることのできる串団子の本数の最大値を求めるプログラムを作成せよ．

入力は以下の形式で与えられる． > $ N $ $ A_1 $ $ A_2 $ $ \cdots $ $ A_N $

JOI 君が作ることのできる串団子の本数の最大値を $ 1 $ 行で出力せよ．

### 小課題 1. ( $ 6 $ 点) $ N = 1 $ ． 2. ( $ 9 $ 点) $ N \leqq 2 $ ． 3. ( $ 10 $ 点) $ A_i $ は $ 3 $ の倍数である ( $ 1 \leqq i \leqq N $ )． 4. ( $ 17 $ 点) $ A_i = 2 $ ( $ 1 \leqq i \leqq N $ )． 5. ( $ 21 $ 点) $ A_i \leqq 3 $ ( $ 1 \leqq i \leqq N $ )． 6. ( $ 37 $ 点) 追加の制約はない． ### Sample Explanation 1 色 $ 1 $ の団子を $ 3 $ 個使った串団子を $ 1 $ 本と，色 $ 2 $ の団子を $ 1 $ 個と色 $ 3 $ の団子を $ 2 $ 個使った串団子を $ 1 $ 本の合計 $ 2 $ 本を作ることができる． $ 1 $ つ目の串団子は $ |1 - 1| = 0 \leqq 1 $ ， $ 2 $ つ目の串団子は $ |2 - 3| \leqq 1 $ ， $ |3 - 3| \leqq 1 $ よりこの団子の選び方は条件を満たす． $ 2 $ 本より多くの串団子を作ることはできないため， $ 2 $ を出力する． この入力例は小課題 $ 5, 6 $ の制約を満たす． ### Sample Explanation 2 色 $ 1 $ の団子を $ 3 $ 個使った串団子を $ 33 $ 本作ることができる． $ 33 $ 本より多くの串団子を作ることはできないため， $ 33 $ を出力する． この入力例は小課題 $ 1, 2, 3, 6 $ の制約を満たす． ### Sample Explanation 3 色 $ 1 $ の団子を $ 3 $ 個使った串団子を $ 1 $ 本と，色 $ 1 $ の団子を $ 2 $ 個と色 $ 2 $ の団子を $ 1 $ 個使った串団子を $ 1 $ 本，色 $ 2 $ の団子を $ 3 $ 個使った串団子を $ 1 $ 本の合計 $ 3 $ 本を作ることができる． $ 3 $ 本より多くの串団子を作ることはできないため， $ 3 $ を出力する． この入力例は小課題 $ 2, 6 $ の制約を満たす． ### Sample Explanation 4 この入力例は小課題 $ 5, 6 $ の制約を満たす． ### Sample Explanation 5 この入力例は小課題 $ 1, 2, 3, 5, 6 $ の制約を満たす． ### Constraints - $ 1 \leqq N \leqq 200\,000 $ ． - $ 0 \leqq A_i \leqq 10^9 $ ( $ 1 \leqq i \leqq N $ )． - 入力される値はすべて整数である．