問題文

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 君が作ることのできる串団子の本数の最大値を求めるプログラムを作成せよ．

制約

• 1 \leqq N \leqq 200\,000．
• 0 \leqq A_i \leqq 10^9 (1 \leqq i \leqq N)．
• 入力される値はすべて整数である．

小課題

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 点) 追加の制約はない．

入力例 1

3
3 1 2

出力例 1

2

色 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 の制約を満たす．

入力例 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 の制約を満たす．