The popular idol Ninomae Ina'nis is hosting a New Year concert! Many of her fans, known as Takodachis, have come out to watch her perform. At the reception, there are Takodachis waiting in line. Initially, the
Takodachi has height
. Seeing her Takodachis with different heights, she starts to wonder if the taller ones will block the shorter Takodachis in the concert. That's when she came up with the brilliant idea of making them all have the same height.
To do so, Ina can perform the following operation: choose two Takodachis indexed at and
such that
. Then, she will increment the
Takodachi's height by
and increment the
Takodachi's height by
.
What is the minimum possible height such that all Takodachis' height can be equal to it after some, possibly zero, number of operations?
Constraints
Subtask 1 [40%]
Subtask 2 [60%]
No additional constraints.
Input Specification
The first line contains an integer , the number of Takodachis.
The next line contains space-separated integers, with the
integer
indicating the height of the
Takodachi.
Output Specification
If it is impossible to make all Takodachis the same height, output .
Otherwise, output the minimum possible height such that all Takodachis can be equal to that height after some, possibly zero, number of operations.
Sample Input
4
1 2 3 4
Sample Output
10
Comments