Problem: You are given a sequence of n integers a1, a2, ..., an. 

Determine a real number x such that the weakness of the sequence a1 - x, a2 - x, ..., an - 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.

Input

The first line contains one integer n (1 ≤ n ≤ 200 000), the length of a sequence.

The second line contains n integers a1, a2, ..., an (|ai| ≤ 10 000).

Output

Output a real number denoting the minimum possible weakness of a1 - x, a2 - x, ..., an - x. Your answer will be considered correct if its relative or absolute error doesn't exceed 10 - 6.

Examples

Input

3
1 2 3


Output

1.000000000000000


Input

4
1 2 3 4


Output

2.000000000000000


Input

10
1 10 2 9 3 8 4 7 5 6


Output

4.500000000000000

Note

For the first case, the optimal value of x is 2 so the sequence becomes  - 1, 0, 1 and the max poorness occurs at the segment "-1" or segment "1". The poorness value (answer) equals to 1 in this case. 

For the second sample the optimal value of x is 2.5 so the sequence becomes  - 1.5, - 0.5, 0.5, 1.5 and the max poorness occurs on segment "-1.5 -0.5" or "0.5 1.5". The poorness value (answer) equals to 2 in this case.

Solution (in JAVA):

Solution:
import java.io.*;
import java.util.*;
public class Sol{
	public static double dpmax[] = new double[200001];
	public static double dpmin[] = new double[200001];
	public static double min;
	public static double max;
	public static int arr[];
	public static int n;
    public static void main(String[] args) throws IOException{
    	FastScanner sc = new FastScanner();
    	n = sc.nextInt();
    	arr = new int[n];
    	for(int i=0; i<n; i++) {
    		arr[i] = sc.nextInt();
    	}
    	double err = 1e-11;
    	double r = 1e6;
    	double l = -1e6;
    	while(r-l>err) {
    		double m1 = l + (r-l)/3;
    		double m2 = r - (r-l)/3;
    		double f1 = func(m1);
    		double f2 = func(m2);
        	if(f1<f2) {
        		r = m2;
        	}else {
        		l = m1;
        	}
    	}
    	System.out.println(func(l));
    	
    }
    public static double func(double delt) {
    	dpmax[0] = arr[0]-delt;
    	dpmin[0] = arr[0]-delt;
    	max = dpmax[0];
    	min = dpmin[0];
    	for(int i=1; i<n; i++) {
    		dpmax[i] = arr[i]-delt + Math.max(0, dpmax[i-1]);
    		dpmin[i] = arr[i]-delt + Math.min(0, dpmin[i-1]);
    		min = Math.min(dpmin[i], min);
    		max = Math.max(max, dpmax[i]);
    	}
    	return Math.max(Math.abs(min), Math.abs(max));
    }
	public static class FastScanner {
		BufferedReader br;
		StringTokenizer st;

		public FastScanner(String s) {
			try {
				br = new BufferedReader(new FileReader(s));
			} catch (FileNotFoundException e) {
				e.printStackTrace();
			}
		}

		public FastScanner() {
			br = new BufferedReader(new InputStreamReader(System.in));
		}

		String nextToken() {
			while (st == null || !st.hasMoreElements()) {
				try {
					st = new StringTokenizer(br.readLine());
				} catch (IOException e) {
					e.printStackTrace();
				}
			}
          return st.nextToken();
		}

		String nextLine() {
			st = null;
			try {
				return br.readLine();
			} catch (IOException e) {
				e.printStackTrace();
			}
			return null;
		}

		int nextInt() {
			return Integer.parseInt(nextToken());
		}

		long nextLong() {
			return Long.parseLong(nextToken());
		}

		double nextDouble() {
			return Double.parseDouble(nextToken());
		}
	}
}