USACO 2013 March Silver - Poker Hands

Bessie와 친구들은 1부터 N(1 <= N <= 100,000)까지 등급이 매겨진 카드를 가지고 특이한 방식의 포커를 하고 있다(보통은 N = 13). 게임 방식은 간단하다. i부터 j까지 등급의 카드가 한 개씩 있으면 “straight”라고 하고, 그 카드들은 없앤다.

Bessie는 i등급의 카드를 a_i개씩 가지고 있다. 모든 카드를 없애기 위해서 필요한 최소 실행 수를 구하여라.

PROBLEM NAME : poker

INPUT FORMAT

Line 1 : 정수 N이 주어진다.

Line 2~N+1 : i등급의 카드의 개수 a_i가 주어진다.

OUTPUT FORMAT

Line 1 : 모든 카드를 없애기 위해서 필요한 최소의 실행 수를 출력한다.

SAMPLE INPUT

5 2 4 1 2 3

SAMPLE OUTPUT

6

http://www.usaco.org/index.php?page=viewproblem2&cpid=262