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?
Subtask 1 [40%]
Subtask 2 [60%]
No additional constraints.
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.
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.
4 1 2 3 4