Colin loves music but cannot catch the rhythm well, especially when counting beats! After hard research on music theory, Colin found a hidden theorem: There won't be a note crossing the boundary between the beats for modern songs.

To simplify the problem, we assume that a modern song consists of several sequential notes whose lengths are milliseconds. The notes will be played one by one, which means the song will start playing the first note at the time , and the second note at the beginning of the milliseconds, and the third note at the beginning of the milliseconds, and so on.

If the length of the beat is milliseconds, then there should not exist any note that is playing but not starting to play at the beginning of the milliseconds, for any non-negative integer . Formally, there should not exist any note such that but for any non-negative integer .

Now Colin has received a new song from Eva, and he wants to practice counting beats before he sings for Eva. To challenge himself, Colin wants to find the smallest possible length of a beat, such that it satisfies the theorem. Can you help him?

The first line contains a single integer , representing the number of notes in the song. 

The second line contains  integers , representing the length of each note.

Output a single integer, representing the minimum possible length of a beat.

5
1 2 3 6 5

6

5
1 2 3 4 5

10