D. William and Cornmeal
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

William has baked a cornmeal pudding pone! They have invited all their friends over to share the dessert. However, they need your help to divide it evenly among all friends.

William wants all of their friends to have an equal number of slices. However, they don't know how many friends will actually show up. Friends show up in groups (where the total number of groups is $$$N$$$), and William cuts the pone in the following manner:

  1. The $$$i$$$th group of friends shows up, which consists of $$$a_i$$$ people.
  2. If the pone is currently cut into $$$s$$$ slices, William cuts the pone into $$$k \cdot s$$$ equal slices for some integer $$$k$$$, such that each person present ($$$a_1 + ... + a_i$$$ people total) can eat an equal number of slices. (But they don't eat it yet!)

The pone starts off unsliced. William wants to know – after everyone (all $$$N$$$ friend groups) show up, what's the minimum number of slices the cake will be cut into that satisfies the given technique?

See the notes for a more detailed example.

Input

The first line contains an integer $$$N$$$ ($$$1 \le N \le 10$$$), the number of friend groups.

The next line contains $$$N$$$ integers $$$a_1,...,a_N$$$ ($$$1 \le a_i \le 10$$$), representing the number of friends in each friend group.

Output

Output a single integer, the minimum number of slices the cake will be cut into.

Example
Input
3
2 3 10
Output
30
Note

The example proceeds in the following manner:

  1. The first group of friends shows up, consisting of 2 people. The pone is initially unsliced, so William slices it into two halves, such that each friend gets a half.
  2. The second group of friends shows up, consisting of 3 people, so there are now 5 total people. William slices each half into 5 pieces, so there are 10 slices total and each friend gets 2 slices.
  3. The third group of friends shows up, consisting of 10 people, so there are now 15 total people. Each of the 10 slices can now be sliced into thirds, so there are 30 slices total and each friend gets 2 slices.

    It can be shown that this is the least number of slices possible that satisfies the requirements.