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.OutputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.StringTokenizer;
import java.io.IOException;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.InputStream;

/**
 * Built using CHelper plug-in
 * Actual solution is at the top
 *
 * @author Artem Gilmudinov
 */
public class Main {
    public static void main(String[] args) {
        InputStream inputStream = System.in;
        OutputStream outputStream = System.out;
        Reader in = new Reader(inputStream);
        PrintWriter out = new PrintWriter(outputStream);
        TaskC solver = new TaskC();
        solver.solve(1, in, out);
        out.close();
    }

    static class TaskC {
        int[] a;
        int n;

        public void solve(int testNumber, Reader in, PrintWriter out) {
            n = in.ni();
            a = new int[n];
            Helper.fillIntArray(in, a);
            double left, right, mid1, mid2, res1, res2;
            left = -1e5;
            right = 1e5;
            res1 = res2 = 0;
            for (int i = 0; i < 100; i++) {
                mid1 = left + (right - left) / 3;
                mid2 = right - (right - left) / 3;
                res1 = check(mid1);
                res2 = check(mid2);
                if (res1 >= res2) {
                    left = mid1;
                } else {
                    right = mid2;
                }
            }
            out.println(String.format("%.12f", res1));
        }

        public double check(double x) {
            double prevMin, prevMax;
            prevMin = prevMax = a[0] - x;
            double min = prevMin;
            double max = prevMax;
            for (int i = 1; i < n; i++) {
                prevMin = Math.min(prevMin + a[i] - x, a[i] - x);
                prevMax = Math.max(prevMax + a[i] - x, a[i] - x);
                min = Math.min(min, prevMin);
                max = Math.max(max, prevMax);
            }
            return Math.max(Math.abs(min), Math.abs(max));
        }

    }

    static class Helper {
        public static void fillIntArray(Reader in, int[] a) {
            for (int i = 0; i < a.length; i++) {
                a[i] = in.ni();
            }
        }

    }

    static class Reader {
        private BufferedReader in;
        private StringTokenizer st = new StringTokenizer("");
        private String delim = " ";

        public Reader(InputStream in) {
            this.in = new BufferedReader(new InputStreamReader(in));
        }

        public String next() {
            if (!st.hasMoreTokens()) {
                st = new StringTokenizer(rl());
            }
            return st.nextToken(delim);
        }

        public String rl() {
            try {
                return in.readLine();
            } catch (IOException e) {
                throw new RuntimeException(e);
            }
        }

        public int ni() {
            return Integer.parseInt(next());
        }

    }
}