You are given a sequence of n integers *a*<sub class="lower-index">1</sub>, *a*<sub class="lower-index">2</sub>, ..., *a*<sub class="lower-index">*n*</sub>. 

Determine a real number *x* such that the weakness of the sequence *a*<sub class="lower-index">1</sub> - *x*, *a*<sub class="lower-index">2</sub> - *x*, ..., *a*<sub class="lower-index">*n*</sub> - *x* is as small as possible.

The weakness of a sequence is defined as the maximum value of the poorness over all segments (contiguous subsequences) of a sequence.

The poorness of a segment is defined as the absolute value of sum of the elements of segment.
The first line contains one integer *n* (1 ≤ *n* ≤ 200 000), the length of a sequence.

The second line contains *n* integers *a*<sub class="lower-index">1</sub>, *a*<sub class="lower-index">2</sub>, ..., *a*<sub class="lower-index">*n*</sub> (|*a*<sub class="lower-index">*i*</sub>| ≤ 10 000).
#include<cstdio>
using namespace std;
int a1[200000];
int main()
{
    int n;double l=-10000,r=10000,md,a,b,c,d;
    scanf("%d",&n);
    for(int i=0;i<n;++i)scanf("%d",a1+i);
    while(r-l>1e-12)
    {
        md=(l+r)/2;a=-10001;b=10001;c=d=0;
        for(int i=0;i<n;++i)
        {
            c+=a1[i]-md;if(c<0)c=0;if(c>a)a=c;
            d+=a1[i]-md;if(d>0)d=0;if(d<b)b=d;
        }
        if(a+b>0)l=md;else r=md;
    }
    printf("%.9f\n",a);
}