Whitespace

Whitespace는 공백과 줄 바꿈만으로 코딩하는 프로그래밍 언어이다. 공백은 SP, 줄 바꿈은 NL로 나타낸다.

영선이에게는 Whitespace로 작성한 프로그램이 있고, 이 프로그램은 길이가 $N$인 수열 $L$로 나타낼 수 있다. $L_i$는 $i$번 줄에 있는 SP의 개수이고, 모든 줄은 NL로 끝난다. 즉, 소스 코드는 $L_0$개의 SP, NL, $L_1$개의 SP, NL, $\ldots$, $L_{N-1}$개의 SP, NL로 이루어져 있다.

오늘 영선이는 효빈이가 만든 에디터로 이 프로그램을 입력하려고 한다. 에디터의 커서는 문서의 처음이나 끝, 또는 인접한 두 문자 사이 어디에나 둘 수 있다. 커서를 옮기는 데에는 키 입력이 필요하지 않다.

에디터에는 다음 3가지 특별한 키가 있다.

• SPACE: 현재 커서 위치에 SP를 하나 삽입한다.
• DELETE: 커서 바로 오른쪽에 있는 SP를 삭제한다. 오른쪽 문자가 NL이면 사용할 수 없다.
• RETURN: NL을 하나 입력한 다음 SP를 $K$개 입력한다. $K$는 커서가 있는 줄의 SP 개수와 같다. 커서 바로 오른쪽 문자가 NL일 때만 사용할 수 있다. 예를 들어 문서가 SP NL SP SP NL SP SP SP NL일 때 두 번째 NL 앞에서 RETURN을 누르면 문서는 SP NL SP SP NL SP SP NL SP SP SP NL이 된다.

지금 에디터에는 NL 하나만 입력되어 있다. $L$이 주어졌을 때, 소스 코드를 완성하는 데 필요한 키 입력 횟수의 최솟값을 구하는 프로그램을 작성하시오.

첫째 줄에 $N$이 주어진다. 둘째 줄에 $L_0, L_1, \ldots, L_{N-1}$이 공백으로 구분되어 주어진다.

• $1 \le N \le 50$
• $0 \le L_i \le 1\,000\,000$

첫째 줄에 소스 코드를 완성하는 데 필요한 키 입력 횟수의 최솟값을 출력한다.

첫 번째 예제에서는 다음과 같이 6번의 키 입력으로 문서를 완성할 수 있다.

• NL
• SP NL
• SP SP NL
• SP SP SP NL
• SP SP SP NL SP SP SP NL
• SP SP SP NL SP SP SP NL SP SP SP NL
• SP SP SP NL SP SP NL SP SP SP NL