What do cows drink? Milk!
At least, that's what Bessie thinks. Bessie the cow loves milk, and has decided today is the day to pay homage to her favorite drink in the form of her newest art installation: The Wall of Milk. The Wall of Milk is just a row of $$$n$$$ glasses, each containing the exact same amount of milk. Bessie has already collected $$$n$$$ glasses of milk, but she still needs to even them out to make The Wall of Milk.
Of course, Bessie could just drink some of the milk from each glass until they were all equal, but she quickly realizes that she could pour the milk from one glass to another! Hooves aren't the best for holding glasses though, so to minimize the chance of ruining her art piece Bessie only pours some milk from one glass to another at most once. Given this, she wonders: how high can The Wall of Milk be?
The first line contains a single integer, $$$1 \leq n \leq 10^5$$$, representing the number of glasses Bessie has.
The next line then contains $$$n$$$ integers $$$1 \leq a_1, \ldots, a_n \leq 10^9$$$, where $$$a_i$$$ represents the units of milk in glass $$$i$$$.
Output a single number, the maximum amount of milk in every glass that Bessie could achieve.
5 1 2 3 4 5
2
3 1 5 5
3.0
In the first test case, Bessie can pour one unit of milk from the third glass into the first glass, so the glasses now contain [2, 2, 2, 4, 5] units of milk respectively. Then Bessie can create a Wall of Milk with height 2 by drinking from the fourth and fifth glasses. It can be shown that this is the maximum height Bessie can achieve.
