물 나누기

과학자 Arthur C. McDonell은 매우 복잡한 화학 실험을 하고 있다. 이 실험은 용기의 모든 컬럼에 정해진 비율로 물을 붓는, 아주 단순한 작업을 아주 많이 필요로 한다. 지루한 수작업에 지친 그는 작업을 자동화하려고 했다.

어느 날 그는 세 갈래 관을 사용해 물의 흐름을 나누는 아이디어를 떠올렸다. 예를 들어 두 컬럼에 1 : 1의 비율로 물을 붓고 싶다면, 세 갈래 관 하나로 하나의 수원을 둘로 나눌 수 있다.

그는 이 아이디어를 적용해 수도꼭지 하나에서 나오는 물을 실험 용기에 임의의 비율로 나누어 붓고 싶었지만, 다음과 같은 조건에서 오는 제약 때문에 일반적으로는 배치를 구성할 수 없다는 사실이 점차 드러났다.

1. 그가 사용하는 용기에는 컬럼이 가로로 나란히 있고, 각 컬럼에는 고유한 용량이 있다. 컬럼의 순서를 바꿀 수는 없다.
2. 유리관, 고무관, 세 갈래 관은 충분히 많다. 세 갈래 관은 항상 물의 흐름을 1 : 1의 비율로 나눈다.
3. 또한 그의 실험실에는 수도꼭지가 충분히 많지만, 모두 같은 높이에 있다.
4. 세 갈래 관으로 두 물의 흐름을 합칠 수는 없다. 게다가 관에서 나오는 각 물의 흐름은 정확히 하나의 컬럼에 부어져야 한다. 물을 하수구로 버릴 수 없고, 하나의 컬럼에 둘 이상의 관에서 물을 부을 수도 없다.

1. 물은 아래로만 흐른다. 따라서 관을 수도꼭지 위에 놓을 수 없고, 다른 관의 출구 아래에도 놓을 수 없다. 게다가 관은 서로 교차할 수 없다.

그래도 Arthur는 포기하고 싶지 않았다. 임의의 비율로 하나에서 여럿으로 나누는 것은 불가능하지만, 그는 사용하는 수도꼭지의 수를 최소화하기로 했다. 그는 컬럼의 수와 각 컬럼을 채울 비율이 주어졌을 때, 용기에 물을 붓는 데 필요한 최소 수도꼭지 수를 계산하는 프로그램을 작성해 달라고 당신에게 부탁했다.

입력은 정수 열로 이루어진다.

첫 번째 정수는 용기의 컬럼 수 N을 나타낸다. 이어서 N개의 정수가 각 컬럼을 채워야 하는 용량을 나타낸다. 이 부분의 i번째 정수는 i번째 컬럼에 물을 부을 비율을 나타낸다.

N ≤ 100이고, 모든 i에 대해 vi ≤ 1000000이라고 가정할 수 있다.

작업을 완료하는 데 필요한 최소 수도꼭지 수를 출력한다.