|시간 제한||메모리 제한||제출||정답||맞은 사람||정답 비율|
|8 초 (추가 시간 없음)||512 MB||0||0||0||0.000%|
A scientist Arthur C. McDonell is conducting a very complex chemical experiment. This experiment requires a large number of very simple operations to pour water into every column of the vessel at the predetermined ratio. Tired of boring manual work, he was trying to automate the operation.
One day, he came upon the idea to use three-pronged tubes to divide the water flow. For example, when you want to pour water into two columns at the ratio of 1 : 1, you can use one three-pronged tube to split one source into two.
He wanted to apply this idea to split water from only one faucet to the experiment vessel at an arbitrary ratio, but it has gradually turned out to be impossible to set the configuration in general, due to the limitations coming from the following conditions:
Still, Arthur did not want to give up. Although one-to-many division at an arbitrary ratio is impossible, he decided to minimize the number of faucets used. He asked you for a help to write a program to calculate the minimum number of faucets required to pour water into the vessel, for the number of columns and the ratio at which each column is going to be filled.
The input consists of an integer sequence.
The first integer indicates N, the number of columns in the vessel. Then the following N integers describe the capacity by which each column should be filled. The i-th integer in this part specifies the ratio at which he is going to pour water into the i-th column.
You may assume that N ≤ 100, and for all i, vi ≤ 1000000.
Output the number of the minimum faucet required to complete the operation.
2 1 1
2 3 1
2 2 1
4 3 1 1 3
3 1 2 1
5 1 2 3 4 5
7 8 8 1 1 2 4 8