34025번 - 창하의 급식실 탁자 이야기

문제

KSA 급식실에는 긴 직사각형 탁자 하나가 있으며, 이 탁자는 두 명이 서로 마주 보고 앉는 2ドル\times M$ 격자 모양으로 되어 있다.

학생들은 자신이 함께 점심을 먹고 싶은 친구들과 무리를 지어 점심을 먹는데, 무리의 개수는 총 $N$개이다. 모든 학생들은 정확히 하나의 무리에 속하며 한 명으로 구성된 무리도 존재할 수 있다. 서로 다른 무리에 속한 학생들은 이웃하거나 마주 보고 앉을 수 없다.

예를 들어 $M = 3$인 아래의 상황에서 학생 A와 서로 다른 무리에 속한 학생은 빗금친 의자에 앉을 수 없다.

KSA 예산 관리자인 창하는 예산을 절약하기 위해 $M$을 최소한으로 줄이고자 한다. 모든 학생들이 동시에 앉을 수 있는 방법이 존재하도록 $M$의 최솟값을 구해주자.

입력

첫 번째 줄에 무리의 개수를 나타내는 정수 $N$$(1 \le N \le 2 \times 10^5)$이 주어진다.

다음 $N$개의 줄 중 $i$번째 줄에 $i$번째 무리에 속한 학생 수가 주어진다. 각 무리의 학생 수는 1ドル$명 이상 2ドル \times 10^5$명 이하이다.

출력

학생들이 모두 탁자에 동시에 앉을 수 있는 방법이 존재하도록 하는 $M$의 최솟값을 출력한다.

제한

힌트