시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 128 MB 38 24 22 73.333%

문제

다항식을 계산하기 위해 고안된 계산기가 있다. 이 계산기에는 0부터 9까지의 숫자와 +, ×(곱하기), x, =의 14개의 키가 있다.

예를 들어 이 계산기를 이용하여 x^3 + x + 11을 계산하려면 x, ×, x, ×, x, +, x + 1, 1, = 을 누르면 된다. 또 x^3 + 2x^2 + 11을 계산하기 위해서는 x, +, 2, ×, x, ×, x, +, 1, 1, = 을 누르면 된다.

일반적인 계산기라면 x, +, 2, ×, x, ×, x, +, 1, 1, = 을 x + 2x^2 + 11로 인식하겠지만, 이 계산기는 추가 메모리가 없기 때문에 계산을 할 때에 계산 직전에 계산기에 저장되어 있던 값에 계산을 한다. 즉 x, +, 2, ×, x, ×, x, +, 1, 1, = 을 입력하면 계산기에는 차례로 x, x+2, x^2+2x, x^3+2x^2, x^3+2x^2+11 이 입력되는 것이다.

문제를 단순하게 하기 위해서 최고차항의 계수는 항상 1이라고 가정하자. 또 음수 계수는 고려하지 않기로 하자.

다항식이 주어졌을 때, 이 계산기로 주어진 다항식을 계산하려면 계산기를 최소 몇 번 눌러야 하는지를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 다항식의 차수 N(1≤N≤10,000)이 주어진다. 다음 줄에는 다항식의 계수가 최고차항부터 주어진다. 최고차항의 계수는 항상 1이며 모든 계수는 0 이상이다. 모든 계수는 1,000,000,000을 넘지 않는다.

출력

첫째 줄에 계산기를 누르는 최소 횟수를 출력한다.

예제 입력

3
1 0 1 11

예제 출력

11

힌트