완충 뷔페

드디어 친구들을 초대해 맛있는 뷔페를 즐길 수 있게 되었다! 하지만 여전히 사회적 거리 두기를 고려해야 한다. 게다가 친구들이 여러 나라에서 오기 때문에, 각 나라의 사회적 거리 두기 규칙이 조금씩 다르다. 예를 들어 미국에서 온 친구는 다른 사람과 최소 $2$미터 떨어져 앉아야 하고, 프랑스에서 온 친구는 $1$미터만 떨어져 앉으면 된다.

모든 친구가 하나의 큰 원형 테이블 둘레에 앉기를 원한다. 각 친구가 자기 나라의 사회적 거리 두기 규칙을 지키도록 자리를 배치하려고 한다. 조금 더 쉽게 만들기 위해, 테이블에 앉은 두 사람 사이의 거리는 원둘레를 따라 계산한다. 모든 사람이 사회적 거리 두기 규칙을 지키며 앉을 수 있는 테이블 둘레의 최솟값은 얼마인가?

입력은 다음과 같다.

• 한 줄에 정수 $n$ ($2 \le n \le 10^{5}$)이 주어진다. 이는 테이블에 앉는 사람 수(자신 포함)이다.
• 한 줄에 $n$개의 정수 $d\_1, \dots, d\_n$ ($1 \le d\_i \le 10^{9}$)이 주어진다. 이는 각 사람이 다른 사람과 떨어져 앉아야 하는 거리(테이블 둘레를 따라 측정)를 미터 단위로 나타낸다.

모든 사람이 사회적 거리 두기 규칙을 지키며 앉을 수 있는 테이블 둘레의 최솟값을 미터 단위로 출력한다.