Problem: Let's assume that we have a sequence of doubles a1, a2, ..., a|a| and a double variable x. You are allowed to perform the following two-staged operation:

  1. choose an index of the sequence element i (1 ≤ i ≤ |a|); 
  2. consecutively perform assignments: <image>. 



Let's use function g(a, x) to represent the largest value that can be obtained from variable x, using the described operation any number of times and sequence a.

Sereja has sequence b1, b2, ..., b|b|. Help Sereja calculate sum: <image>. Record [bi, bi + 1, ..., bj] represents a sequence containing the elements in brackets in the given order. To avoid problems with precision, please, print the required sum divided by |b|2.

Input

The first line contains integer |b| (1 ≤ |b| ≤ 3·105) — the length of sequence b. The second line contains |b| integers b1, b2, ..., b|b| (1 ≤ bi ≤ 105).

Output

In a single line print a real number — the required sum divided by |b|2. Your answer will be considered correct if its absolute or relative error won't exceed 10 - 6.

Examples

Input

5
1 2 3 4 1


Output

1.238750000000000

Solution (in JAVA):

Solution:
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.util.Arrays;
import java.util.Comparator;
import java.util.StringTokenizer;

public class Main223E {

    private FastScanner in;
    private PrintWriter out;

    private class Item {
        private int value;
        private int pos;

        Item(int value, int pos) {
            this.value = value;
            this.pos = pos;
        }
    }

    public void solve() throws IOException {
        int COUNT = 22;

        int n = in.nextInt();
        Item[] array = new Item[n];
        for(int i = 0; i < n; i++) {
            array[i] = new Item(in.nextInt(), i);
        }

        int[] prev = new int[n];
        int[] next = new int[n];
        for(int i = 0; i < n; i++) {
            prev[i] = i - 1;
            next[i] = i + 1;
        }

        Arrays.sort(array, new Comparator<Item>() {
            @Override
            public int compare(Item o1, Item o2) {
                return o1.value - o2.value;
            }
        });

        double result = 0;
        long[] left = new long[COUNT];
        long[] right = new long[COUNT];
        double[] coeff = new double[2 * COUNT];
        int[] pow2 = new int[COUNT];
        pow2[0] = 2;
        for(int i = 1; i < pow2.length; i++) {
            pow2[i] = pow2[i - 1] << 1;
        }

        for(int i = 0; i < n; i++) {
            int countLeft = 1;
            int currPos = array[i].pos;
            left[0] = currPos;
            while(currPos != -1 && countLeft < COUNT) {
                left[countLeft++] = prev[currPos];
                currPos = prev[currPos];
            }
            int countRight = 1;
            currPos = array[i].pos;
            right[0] = currPos;
            while(currPos != n && countRight < COUNT) {
                right[countRight++] = next[currPos];
                currPos = next[currPos];
            }

            for(int j = 0; j < COUNT; j++) {
                coeff[j] = 0;
            }

            for(int j = 1; j < countLeft; j++) {
                int c = Math.min(countRight, COUNT + 2 - j);
                for(int k = 1; k < c; k++) {
                    coeff[j + k - 2] += (left[j - 1] - left[j]) * (right[k] - right[k - 1]);
                }
            }

            double res = 0;
            for(int j = 0; j < COUNT; j++) {
                res += coeff[j] / pow2[j];
            }

            result += res * array[i].value;

            currPos = array[i].pos;
            if(next[currPos] != n) {
                prev[next[currPos]] = prev[currPos];
            }
            if(prev[currPos] != -1) {
                next[prev[currPos]] = next[currPos];
            }
        }

        result /= n;
        result /= n;
        out.println(String.format("%.15f", result));
    }

    public void run() {
        try {
            in = new FastScanner(System.in);
            out = new PrintWriter(System.out);
            solve();
            out.close();
        } catch (IOException e) {
            e.printStackTrace();
        }
    }

    class FastScanner {

        BufferedReader br;
        StringTokenizer st;

        FastScanner(InputStream is) {
            br = new BufferedReader(new InputStreamReader(is));
        }

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

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

    public static void main(String[] arg) {
        new Main223E().run();
    }
}