JOI 군은 떡 장인이다. 떡에는 색 1부터 색 \(N\)까지 \(N\)가지 색이 있으며, JOI 군은 색 \(i\) (\(1 \le i \le N\))의 떡을 \(A_i\)개 가지고 있다. JOI 군은 가지고 있는 떡에서 3개를 골라 1개의 꼬치떡을 만들 수 있다. 단, 고른 3개 떡의 색이 \(c_1, c_2, c_3\) (\(1 \le c_1 \le N\), \(1 \le c_2 \le N\), \(1 \le c_3 \le N\))일 때, \(c_1\)과 \(c_2\), \(c_2\)와 \(c_3\), \(c_3\)와 \(c_1\)의 차는 각각 1 이하여야 한다. 즉 다음 조건이 모두 성립해야 한다.
여러 꼬치떡에서 같은 떡을 공유하여 쓸 수 없다. JOI 군은 가지고 있는 떡을 잘 골라 가능한 한 많은 꼬치떡을 만들고 싶다. JOI 군이 가지고 있는 떡에 대한 정보가 주어졌을 때, JOI 군이 만들 수 있는 꼬치떡 개수의 최댓값을 구하는 프로그램을 작성하라. |
입력은 다음 형식으로 주어진다.
\(N\)
\(A_1\) \(A_2\) \(\cdots\) \(A_N\)
제약 조건
- \(1 \le N \le 200{,}000\)
- \(0 \le A_i \le 10^9\) (\(1 \le i \le N\))
- 입력되는 값은 모두 정수이다.
부분문제
- (6점) \(N = 1\)
- (9점) \(N \le 2\)
- (10점) \(A_i\)는 3의 배수이다 (\(1 \le i \le N\)).
- (17점) \(A_i = 2\) (\(1 \le i \le N\)).
- (21점) \(A_i \le 3\) (\(1 \le i \le N\)).
- (37점) 추가 제약 조건 없음.
다음 형식으로 출력한다.
JOI 군이 만들 수 있는 꼬치떡 개수의 최댓값을 1줄에 출력한다.
색 1의 떡 3개를 쓴 꼬치떡 1개와, 색 2의 떡 1개와 색 3의 떡 2개를 쓴 꼬치떡 1개, 합계 2개를 만들 수 있다. 첫 번째 꼬치떡은 \(|1 - 1| = 0 \le 1\), 두 번째 꼬치떡은 \(|2 - 3| \le 1\), \(|3 - 3| \le 1\)이므로 이 고르기는 조건을 만족한다. 2개보다 많은 꼬치떡을 만들 수 없으므로 2를 출력한다.
색 1의 떡 3개를 쓴 꼬치떡 33개를 만들 수 있다. 33개보다 많은 꼬치떡을 만들 수 없으므로 33을 출력한다.
색 1의 떡 3개를 쓴 꼬치떡 1개, 색 1의 떡 2개와 색 2의 떡 1개를 쓴 꼬치떡 1개, 색 2의 떡 3개를 쓴 꼬치떡 1개, 합계 3개를 만들 수 있다. 3개보다 많은 꼬치떡을 만들 수 없으므로 3을 출력한다.