Do you think that magic is simple? That some hand-waving and muttering
incomprehensible blubber is enough to conjure wonderful gardens or a
fireball to burn your enemies to ashes?
The reality is a little more complicated than that. To master skills,
young wizards spend years studying such subjects as magical analysis and
demonology practice.
In fact, Oleg, a student of the Institute of Magic and Common Sorcery
(IMCS) is preparing for an exam. And there’s no way he can calculate the
Dumbledore determinant. As you might have guessed, he asked you to help
him.
Let us remind you the basic definitions just in case you haven’t been
visiting lectures on the theory of nonlinear spells. The Gandalf theorem
states that any part of subspace can be represented as a vector of magic
potentials that is an array of n positive integers.
A Dumbledore determinant of this array equals the
minimum number of elementary magical transformations required to turn the
original array into the array where all elements are equal to one.
One elementary magical transformation turns the original array of
length k into a new array of length k · (k − 1) / 2.
The elements of the new array are greatest common divisors of
each pair of elements of the original array. For example, the
elementary magical transformation of array {2, 3, 3, 6} turns it into array
{gcd(2, 3), gcd(2, 3), gcd(2, 6), gcd(3, 3), gcd(3, 6), gcd(3, 6)},
that is {1, 1, 2, 3, 3, 3}.
Input
The first line contains number n that is the length of
the original array (3 ≤ n ≤ 10 000). Next n lines
contain the elements of array that are positive integers not exceeding 107.
Output
Output Dumbledore determinant for the array given in the input.
If Dumbledore determinant is not defined or it exceeds
1018, output “infinity”.
Samples
input | output |
---|
3
1
2
3
| 1
|
4
2
2
2
2
| infinity
|
Problem Author: Kirill Borozdin
Problem Source: Ural Regional School Programming Contest 2013