레이팅 미적용JOI 君は団子職人である.団子には色 1 から色 N までの N 色あり,JOI 君は色 i ( 1 ≦ i ≦ N ) の団子を A i 個持っている.
JOI 君は持っている団子から 3 個選んで 1 本の 串団子 を作ることができる.ただし,選んだ 3 個の団子の色が
c 1 , c 2 , c 3
( 1 ≦ c 1 ≦ N , 1 ≦ c 2 ≦ N , 1 ≦ c 3 ≦ N )
であるとき, c 1 と c 2 ,
c 2 と c 3 ,
c 3 と c 1
の差はそれぞれ 1 以下でなければならない.
つまり以下の条件がすべて成り立つ必要がある.
|c 1 − c 2 | ≦ 1
|c 2 − c 3 | ≦ 1
|c 3 − c 1 | ≦ 1
複数の串団子で同じ団子を共有して使うことはできない.JOI 君は持っている団子をうまく選んでできるだけ多くの串団子を作りたい.
JOI 君が持っている団子についての情報が与えられたとき,JOI 君が作ることのできる串団子の本数の最大値を求めるプログラムを作成せよ.
1 ≦ N ≦ 200 000 .
0 ≦ A i ≦ 10 9 ( 1 ≦ i ≦ N ).
入力される値はすべて整数である.
( 6 点) N = 1 .
( 9 点) N ≦ 2 .
( 10 点) A i は 3 の倍数である ( 1 ≦ i ≦ N ).
( 17 点) A i = 2 ( 1 ≦ i ≦ N ).
( 21 点) A i ≦ 3 ( 1 ≦ i ≦ N ).
( 37 点) 追加の制約はない.
入力は以下の形式で与えられる.
N
A 1 A 2 ... A N
JOI 君が作ることのできる串団子の本数の最大値を 1 行で出力せよ.
3
3 1 2
2
1
99
33
2
5 6
3
6
0 2 2 3 1 2
3
1
0
0