Long Tape

Interview

Time limit1sMemory limit128 MB

Summary

Choose a nonempty contiguous segment of the given sequence so its arithmetic mean is as small as possible.

Level: Easy1 of 10
Topics: Array
Solved: No attempts yet

Problem

Jaś found a very long tape at home. Without a second thought he wrote a sequence of integers on it, and soon a new game came to his mind.

Jaś wants to cut off some initial (prefix) part and some final (suffix) part of the tape, each part possibly of length $0$ . He would like the arithmetic mean of the numbers (their sum divided by how many there are) on the fragment that is left to be as small as possible. The remaining fragment must contain at least one number.

Find the smallest arithmetic mean he can obtain this way.

Input

The first line contains one integer $n$ ( $1 \le n \le 10^6$ ), the count of numbers written on the tape.

The second line contains $n$ integers $a_1, a_2, \ldots, a_n$ ( $|a_i| \le 10^9$ ), separated by spaces, where $a_i$ is the $i$ -th number written on the tape.

Output

Print a single number on one line, rounded to two decimal places, equal to the minimum arithmetic mean achievable by the numbers left on the tape.

Examples2

Example 1
Input
```
7
3 4 2 2 2 5 8
```
Expected output
```
2.00
```
Example 2
Input
```
1
5
```
Expected output
```
5.00
```