다항식 계산기

다항식을 계산하기 위한 특수한 계산기가 있다. 이 계산기에는 숫자 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, 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을 넘지 않는다.

계산기를 눌러야 하는 최소 횟수를 첫째 줄에 출력한다.