시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 (추가 시간 없음) 1024 MB270837336.500%

문제

각고의 노력 끝에 현자의 돌을 얻은 연금술사는 모든 물질로 금을 만들 수 있는 것은 아니라는 사실을 깨닫고 절망하였다. 그러나, 그는 현자의 돌을 이용해 가치가 낮은 광물로 가치가 높은 광물을 만들 수 있다는 사실을 발견하였다. 물론, 가치가 높은 광물을 사용해서 얻은 결과물의 가치가 낮을 수도 있다.

구체적으로, 광물 k(k ≥ 1)개와 현자의 돌을 이용해 새로운 광물을 만드는 경우를 생각해 보자. 사용한 광물 k개의 가치를 각각 x1, x2, …, xk라 할 때, S = {x1, x2, …, xk}에 포함되지 않는 가장 작은 음이 아닌 정수 MEX(S)가 최종 산물의 가치가 된다. 예를 들어, 가치가 각각 0, 1, 4, 2, 1인 광물과 현자의 돌을 이용해 새로운 광물을 만드는 경우, MEX({0, 1, 4, 2, 1}) = 3이므로 결과 광물의 가치는 3이 된다.

현재 연금술사는 가치가 0, 1, 2, …, (− 1)인 광물들을 각각 c0, c1, c2, …, cN-1개씩 가지고 있다. 연금술사는 이 광물들과 현자의 돌을 이용해 새로운 광물을 만드는 과정을 여러 번 반복할 수 있다. 결과물로 나온 광물도 다시 재료로 사용할 수 있다. 이 과정에서 현자의 돌은 무한히 사용할 수 있다.

연금술사의 목표는 최종적으로 단 하나의 광물만을 남기면서 그 광물의 가치를 최대로 하는 것이다. 단, 광물을 사용하지 않고 버릴 수는 없다.

연금술사가 최종적으로 얻게 될 단 하나의 광물의 가치의 최댓값을 구하여라.

입력

첫 줄에 정수 N이 주어진다.

두 번째 줄에 N개의 정수 c0, c1, …, cN-1이 공백으로 구분되어 주어진다. 단, 연금술사는 적어도 하나 이상의 광물을 갖고 있다.

출력

첫 줄에 최종적으로 남은 광물 하나의 가치의 최댓값을 출력한다.

제한

  • 1 ≤ N ≤ 100,000
  • 0 ≤ ci ≤ 109
  • cc+ … + cN-1 ≥ 1

예제 입력 1

1
1

예제 출력 1

1

예제 입력 2

2
0 1

예제 출력 2

1

예제 입력 3

6
1 0 0 0 0 1

예제 출력 3

2

예제 입력 4

5
0 0 0 0 1

예제 출력 4

4

예제 입력 5

5
1 0 1 0 1

예제 출력 5

3

다음은 다섯 번째 예제에 대한 설명이다.

처음에는 가치가 0, 2, 4인 광물이 하나씩 존재한다.

가치가 0인 광물과 현자의 돌을 이용해 가치가 MEX({0}) = 1인 광물을 만들면 남은 광물들의 가치는 1, 2, 4가 된다.

가치가 4인 광물과 현자의 돌을 이용해 가치가 MEX({4}) = 0인 광물을 만들면 남은 광물들의 가치는 0, 1, 2가 된다.

가치가 0, 1, 2인 광물과 현자의 돌을 이용해 가치가 MEX({0, 1, 2}) = 3인 광물을 만들면 가치가 3인 광물 하나만 남고, 이것이 남은 광물의 가능한 최대 가치이다.