좌우 한 줄로 있는 \(N\)개의 장소 각각에 조약돌이 몇 개씩 놓여 있다. 

  철수가 할 수 있는 작업의 종류는 아래 두 가지이다. 

1. 인접한 두 장소에서 임의의 동일한 개수의 조약돌을 가져가기 
2. 한 장소에서 임의의 개수의 조약돌을 가져가기

  어떤 장소에 조약돌이 더 이상 없는 경우에도 그 장소는 그대로 남아 있어서, 초기에 인접하지 않았던 두 장소가 인접한 것으로 바뀌지 않는다.

  철수는 위의 두 작업 중 하나를 골라서 실행하는 것을 반복하여 모든 조약돌을 가져가려고 한다.

  초기에 각 장소에 있는 조약돌들의 개수를 입력받아, 철수가 할 수 있는 최소의 작업 횟수를 계산하는 프로그램을 작성하라.

  첫 번째 줄에 장소의 개수 \(N\)이 주어진다.

  두 번째 줄에 \(N\)개의 장소 각각에 있는 조약돌 개수가 왼쪽 장소에 해당하는 것부터 순서대로 공백 하나씩을 사이로 두고 주어진다.

• \(2 \le N \le 2 500\)
• 각 장소의 초기 조약돌 개수는 1 이상 \(10^8\) 이하이다.

1. (6점) \(N = 3. \)
2. (11점) \(N \le 15. \)
3. (19점) \(N \le 300. \)
4. (27점) 각 장소의 초기 조약돌 개수가 2 500 이하이다. 
5. (37점) 추가 제약 조건 없음.

첫 번째 줄에 답을 출력한다