문제 보기 - 수열 (BOI14_sequence)

시간 제한 메모리 제한 제출 횟수 통과한 사람 수 비율
1000 ms 256 MiB 305 23 7.54%

승현이는 칠판 위에 $N$에서부터 시작하는 $K$개의 연속하는 양의 정수를 차례대로 적었습니다. 그가 떠날 때, 지학이가 오더니 각 수에서 단 하나의 숫자만을 남기고 다 지워버려, $K$개의 숫자로 구성된 수열만이 남게 되었습니다.

해야 할 일

지학이가 지운 후의 수열이 주어질 때, 승현이가 칠판 위에 가장 먼저 썼을 지도 모르는 $N$들 중 가장 작은 값을 구하세요.

입력 형식

첫 번째 줄에 수열의 길이 $K$가 주어집니다. 두 번째 줄에는 지학이의 수열 $B_{1}, B_{2}, \cdots, B_{K}$ ($0 \le B_{i} \le 9$)가 칠판 위에 쓰인 순서대로 주어집니다.

출력 형식

첫 번째 줄에 승현이가 칠판 위에 가장 먼저 썼을 지도 모르는 $N$들 중 가장 작은 값을 출력합니다.

예제

입력 출력
6
7 8 9 5 1 2
47

참고

$N = 47$이라면 승현이가 칠판 위에 적은 수열은 47 48 49 50 51 52이고 지학이는 잘 지워서(?) 7 8 9 5 1 2를 만들 수 있습니다. 이것보다 작은 $N$에 대해서는 동작하지 않을 것이므로, 답은 47입니다.

채점

서브태스크 1 (9점)

  • $1 \le K \le 1,000$
  • 정답은 1000 이하입니다.

서브태스크 2 (33점)

  • $1 \le K \le 1,000$

서브태스크 3 (25점)

  • $1 \le K \le 100,000$
  • 입력으로 주어지는 수열의 모든 원소는 서로 같습니다.

서브태스크 4 (33점)

  • $1 \le K \le 100,000$

제약 조건

시간 제한: 1초.

메모리 제한: 256 MB