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.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.PriorityQueue;
import java.util.Scanner;
import java.util.StringTokenizer;

public class E579 {

	public static void main(String[] args) throws IOException {
		initReader();
		int n = nextInt();
		long arr[] = new long[n];
		double left = Double.MAX_VALUE;

		double right = Double.MIN_VALUE;
		for (int i = 0; i < n; ++i) {
			arr[i] = nextLong();
			right = Math.max(arr[i], right);
			left = Math.min(arr[i], left);
		}
		int count = 60;
		while (count-- > 0) {
			double mid = (left + right) / 2;
			if (cal(arr, mid)) {
				right = mid;
			} else {
				left = mid;
			}
		}

		System.out.printf("%.7f\n", getAns(arr, right));

	}

	private static double getAns(long[] arr, double mark) {
		double left = 0;
		double right = 0;
		int sign = -1;
		// PriorityQueue<Double> getMin = new PriorityQueue<Double>();
		// PriorityQueue<Double> getMax = new PriorityQueue<Double>();
		double min = 0;
		double max = 0;
	
		double pre = 0;
		for (int i = 0; i < arr.length; ++i) {
			pre += arr[i] - mark;
			double r = pre - min;
			double l = pre - max;
			if (r >= 0) {
				right = Math.max(right, r);
			}
			sign = -sign;
			if (l <= 0) {
				left = Math.min(l, left);
			}
			//getMin.add(pre);
			//getMax.add(-pre);
			min = Math.min(pre, min);
			max = Math.max(pre, max);
		}

		return Math.max(Math.abs(left), right);
	}

	private static boolean cal(long[] arr, double mid) {
		double left = 0;
		double right = 0;
		double min = 0;
		double max = 0;
		double pre = 0;
		for (int i = 0; i < arr.length; ++i) {
			pre += arr[i] - mid;
			double r = pre - min;
			double l = pre - max;
			if (r >= 0) {
				right = Math.max(right, r);
			}
			if (l <= 0) {
				left = Math.min(l, left);
			}
			min = Math.min(pre, min);
			max = Math.max(pre, max);
		}

		if (Math.abs(left) > Math.abs(right)) {
			return true;
		} else {
			return false;
		}
	}

	static BufferedReader reader;
	static StringTokenizer tokenizer;

	public static void initReader() {
		reader = new BufferedReader(new InputStreamReader(System.in));
		tokenizer = new StringTokenizer("");
	}

	static String next() throws IOException {
		while (!tokenizer.hasMoreTokens()) {
			String n = reader.readLine();
			if (n == null) {
				return null;
			}
			tokenizer = new StringTokenizer(n);

		}
		return tokenizer.nextToken();
	}

	static String nextLine() throws IOException {
		return reader.readLine();
	}

	static Integer nextInt() throws IOException {
		String next = next();
		if (next == null) {
			return null;
		}
		return Integer.parseInt(next);
	}

	static long nextLong() throws IOException {
		return Long.parseLong(next());
	}

	static Double nextDouble() throws IOException {
		return Double.parseDouble(next());
	}
}