第25回日本情報オリンピック　二次予選

2025年12月15日
情報オリンピック日本委員会

問題文

JOI 君は団子職人である．団子には色 1 から色 N までの N 色あり，JOI 君は色 i (1 ≦ i ≦ N) の団子を A_i 個持っている．

JOI 君は持っている団子から 3 個選んで 1 本の串団子を作ることができる．ただし，選んだ 3 個の団子の色が c₁, c₂, c₃ (1 ≦ c₁ ≦ N，1 ≦ c₂ ≦ N，1 ≦ c₃ ≦ N) であるとき，c₁ と c₂， c₂ と c₃， c₃ と c₁ の差はそれぞれ 1 以下でなければならない． つまり以下の条件がすべて成り立つ必要がある．

• |c₁ − c₂| ≦ 1
• |c₂ − c₃| ≦ 1
• |c₃ − c₁| ≦ 1

複数の串団子で同じ団子を共有して使うことはできない．JOI 君は持っている団子をうまく選んでできるだけ多くの串団子を作りたい．

JOI 君が持っている団子についての情報が与えられたとき，JOI 君が作ることのできる串団子の本数の最大値を求めるプログラムを作成せよ．

制約

• 1 ≦ N ≦ 200 000．
• 0 ≦ A_i ≦ 10⁹ (1 ≦ i ≦ N)．
• 入力される値はすべて整数である．

小課題

1. (6 点) N = 1．
2. (9 点) N ≦ 2．
3. (10 点) A_i は 3 の倍数である (1 ≦ i ≦ N)．
4. (17 点) A_i = 2 (1 ≦ i ≦ N)．
5. (21 点) A_i ≦ 3 (1 ≦ i ≦ N)．
6. (37 点) 追加の制約はない．

入力

入力は以下の形式で与えられる．
N
A₁   A₂   …   A_N

出力

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

入出力例

入力例 1
3
3   1   2

出力例 1
2

色 1 の団子を 3 個使った串団子を 1 本と， 色 2 の団子を 1 個と色 3 の団子を 2 個使った串団子を 1 本の合計 2 本を作ることができる． 1 つ目の串団子は |1 − 1| = 0 ≦ 1， 2 つ目の串団子は |2 − 3| ≦ 1，|3 − 3| ≦ 1 より， この団子の選び方は条件を満たす． 2 本より多くの串団子を作ることはできないため，2 を出力する．

この入力例は小課題 5, 6 の制約を満たす．

入力例 2
1
99

出力例 2
33

色 1 の団子を 3 個使った串団子を 33 本作ることができる． 33 本より多くの串団子を作ることはできないため，33 を出力する．

この入力例は小課題 1, 2, 3, 6 の制約を満たす．

入力例 3
2
5   6

出力例 3
3

色 1 の団子を 3 個使った串団子を 1 本と， 色 1 の団子を 2 個と色 2 の団子を 1 個使った串団子を 1 本， 色 2 の団子を 3 個使った串団子を 1 本の 合計 3 本を作ることができる． 3 本より多くの串団子を作ることはできないため，3 を出力する．

この入力例は小課題 2, 6 の制約を満たす．

入力例 4
6
0   2   2   3   1   2

出力例 4
3

この入力例は小課題 5, 6 の制約を満たす．

入力例 5
1
0

出力例 5
0

この入力例は小課題 1, 2, 3, 5, 6 の制約を満たす．