Jan is participating in a team contest and, along with his team, is trying to sit in a room full of seats. However, this is not an easy task, as many of these seats are occupied and they want to sit together, meaning the seats where the team members sit must be adjacent.

Now Jan is interested in what the ideal size $$$M$$$ should be for all teams to maximize the number of people seated. Each person must be in a team of size $$$M$$$, and the people in each team must be seated in adjacent seats. The teams must be of more than one person, so $$$M \gt 1$$$.

Help Jan calculate this optimal value of $$$M$$$, given that there are $$$n$$$ groups of adjacent free seats in the room, and the $$$i$$$-th of them consists of $$$a_i$$$ adjacent seats.

Note that if $$$E_M = \sum_{i=1}^n \lfloor\frac{a_i}{M}\rfloor$$$ is the number of teams of size $$$M$$$ that can be seated in the room, the quantity to be maximized is $$$E_M \cdot M$$$. If there are multiple values of $$$M$$$ that give the optimal value of $$$E_M \cdot M$$$, you should respond with the smallest of them.

1. (10 points) $$$n, a_{i} \leq 5 \cdot 10^{3}$$$.
2. (13 points) $$$n, a_{i} \leq 5 \cdot 10^{4}$$$.
3. (16 points) $$$a_{i} \leq 10^{6}$$$.
4. (20 points) $$$n \leq 5 \cdot 10^{3}$$$.
5. (41 points) No additional restrictions.