Page Title

TARNS

In the High Tatras (the highest mountain range in Slovakia) there are N tarns (glaciar mountain lakes) with volumes v₁,...,v_N liters. It's raining a lot and every second 1 liter of water flows into each tarn.

As soon as any tarn is full, all its supply starts flowing into the next tarn (the one with index higher by one). The water overflowing from the last tarn flows into the river and goes away.

Find two times:
How long does it take until the last tarn overflows?
How long does it take until all the tarns are full?

Input

The first line contains the number N (number of lakes), the second line contains N numbers - their volumes.

Output

Write two times (in seconds) rounded to at least two decimal places: how long does it take until the last tarn overflows and when will all tarns be full.

Examples

Input:
4
20 1 1 6
Output:
2.67
20.00

Input:
3
1 3 5
Output:
3.00
3.00

In the first example, after the first second the two middle tarns start overflowing into the last one that alreadty contains 1 liter, so it can hold only 5 more liters. Now 3 liters of water flows into it every second. It will overflow in 5/3 = 1,67 seconds, that's 2,67 seconds since the beginning.

After 20 seconds since the beginning the first tarn overflows too and all the tarns are full.

Tarns Challenge