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.OutputStream;
import java.io.IOException;
import java.io.InputStream;
import java.util.stream.IntStream;
import java.util.Arrays;
import java.util.Random;
import java.util.ArrayList;
import java.math.BigDecimal;
import java.io.OutputStreamWriter;
import java.io.OutputStream;
import java.io.IOException;
import java.io.UncheckedIOException;
import java.util.List;
import java.io.Closeable;
import java.io.Writer;
import java.io.InputStream;

/**
 * Built using CHelper plug-in
 * Actual solution is at the top
 */
public class Main {
    public static void main(String[] args) throws Exception {
        Thread thread = new Thread(null, new TaskAdapter(), "", 1 << 29);
        thread.start();
        thread.join();
    }

    static class TaskAdapter implements Runnable {
        @Override
        public void run() {
            InputStream inputStream = System.in;
            OutputStream outputStream = System.out;
            FastInput in = new FastInput(inputStream);
            FastOutput out = new FastOutput(outputStream);
            ESerejaAndDividing solver = new ESerejaAndDividing();
            solver.solve(1, in, out);
            out.close();
        }
    }

    static class ESerejaAndDividing {
        public void solve(int testNumber, FastInput in, FastOutput out) {
            int n = in.ri();
            int[] b = in.ri(n);
            int[] indices = IntStream.range(0, n).toArray();
            SortUtils.quickSort(indices, (i, j) -> -Integer.compare(b[i], b[j]), 0, n);
            IntegerArrayList prev = new IntegerArrayList();
            IntegerArrayList next = new IntegerArrayList();
            RangeTree rt = new RangeTree(n + 2);
            rt.add(0);
            rt.add(n + 1);
            double ans = 0;
            int lim = 60;
            for (int index : indices) {
                prev.clear();
                prev.add(index + 1);
                for (int i = 0, x = index + 1; i < lim; i++) {
                    int floor = rt.floor(x - 1);
                    if (floor == -1) {
                        break;
                    }
                    x = floor;
                    prev.add(x);
                }
                next.clear();
                next.add(index + 1);

                for (int i = 0, x = index + 1; i < lim; i++) {
                    int ceil = rt.ceil(x + 1);
                    if (ceil == -1) {
                        break;
                    }
                    x = ceil;
                    next.add(x);
                }
                int[] A = prev.getData();
                int[] B = next.getData();
                int aSize = prev.size();
                int bSize = next.size();
                double L = 0;
                double R = 0;
                for (int i = 0; i + 1 < aSize; i++) {
                    L += (double) (A[i] - A[i + 1]) / (1L << i);
                }
                for (int i = 0; i + 1 < bSize; i++) {
                    R += (double) (B[i + 1] - B[i]) / (1L << i);
                }
                ans += b[index] * L * R / 2;
                rt.add(index + 1);
            }

            ans /= n;
            ans /= n;
            out.println(ans);
        }

    }

    static class IntegerArrayList implements Cloneable {
        private int size;
        private int cap;
        private int[] data;
        private static final int[] EMPTY = new int[0];

        public int[] getData() {
            return data;
        }

        public IntegerArrayList(int cap) {
            this.cap = cap;
            if (cap == 0) {
                data = EMPTY;
            } else {
                data = new int[cap];
            }
        }

        public IntegerArrayList(int[] data) {
            this(0);
            addAll(data);
        }

        public IntegerArrayList(IntegerArrayList list) {
            this.size = list.size;
            this.cap = list.cap;
            this.data = Arrays.copyOf(list.data, size);
        }

        public IntegerArrayList() {
            this(0);
        }

        public void ensureSpace(int req) {
            if (req > cap) {
                while (cap < req) {
                    cap = Math.max(cap + 10, 2 * cap);
                }
                data = Arrays.copyOf(data, cap);
            }
        }

        public void add(int x) {
            ensureSpace(size + 1);
            data[size++] = x;
        }

        public void addAll(int[] x) {
            addAll(x, 0, x.length);
        }

        public void addAll(int[] x, int offset, int len) {
            ensureSpace(size + len);
            System.arraycopy(x, offset, data, size, len);
            size += len;
        }

        public void addAll(IntegerArrayList list) {
            addAll(list.data, 0, list.size);
        }

        public int size() {
            return size;
        }

        public int[] toArray() {
            return Arrays.copyOf(data, size);
        }

        public void clear() {
            size = 0;
        }

        public String toString() {
            return Arrays.toString(toArray());
        }

        public boolean equals(Object obj) {
            if (!(obj instanceof IntegerArrayList)) {
                return false;
            }
            IntegerArrayList other = (IntegerArrayList) obj;
            return SequenceUtils.equal(data, 0, size - 1, other.data, 0, other.size - 1);
        }

        public int hashCode() {
            int h = 1;
            for (int i = 0; i < size; i++) {
                h = h * 31 + Integer.hashCode(data[i]);
            }
            return h;
        }

        public IntegerArrayList clone() {
            IntegerArrayList ans = new IntegerArrayList();
            ans.addAll(this);
            return ans;
        }

    }

    static class Bits {
        private Bits() {
        }

        public static long set(long x, int i) {
            return x | (1L << i);
        }

        public static int highestOneBitOffset(long x) {
            if (x < 0) {
                return 63;
            }
            return 63 - Long.numberOfLeadingZeros(x);
        }

        public static int lowestOneBitOffset(long x) {
            return highestOneBitOffset(x & -x);
        }

        public static long tailMask(int n) {
            if (n == 0) {
                return 0;
            }
            return -1L << (64 - n);
        }

        public static long headMask(int n) {
            if (n == 0) {
                return 0;
            }
            return -1L >>> (64 - n);
        }

    }

    static interface IntegerIterator {
        boolean hasNext();

        int next();

    }

    static class RandomWrapper {
        private Random random;
        public static final RandomWrapper INSTANCE = new RandomWrapper();

        public RandomWrapper() {
            this(new Random());
        }

        public RandomWrapper(Random random) {
            this.random = random;
        }

        public RandomWrapper(long seed) {
            this(new Random(seed));
        }

        public int nextInt(int l, int r) {
            return random.nextInt(r - l + 1) + l;
        }

    }

    static class SequenceUtils {
        public static void swap(int[] data, int i, int j) {
            int tmp = data[i];
            data[i] = data[j];
            data[j] = tmp;
        }

        public static boolean equal(int[] a, int al, int ar, int[] b, int bl, int br) {
            if ((ar - al) != (br - bl)) {
                return false;
            }
            for (int i = al, j = bl; i <= ar; i++, j++) {
                if (a[i] != b[j]) {
                    return false;
                }
            }
            return true;
        }

    }

    static interface IntegerComparator {
        public int compare(int a, int b);

    }

    static class FastOutput implements AutoCloseable, Closeable, Appendable {
        private static final int THRESHOLD = 32 << 10;
        private final Writer os;
        private StringBuilder cache = new StringBuilder(THRESHOLD * 2);

        public FastOutput append(CharSequence csq) {
            cache.append(csq);
            return this;
        }

        public FastOutput append(CharSequence csq, int start, int end) {
            cache.append(csq, start, end);
            return this;
        }

        private void afterWrite() {
            if (cache.length() < THRESHOLD) {
                return;
            }
            flush();
        }

        public FastOutput(Writer os) {
            this.os = os;
        }

        public FastOutput(OutputStream os) {
            this(new OutputStreamWriter(os));
        }

        public FastOutput append(char c) {
            cache.append(c);
            afterWrite();
            return this;
        }

        public FastOutput append(double c) {
            cache.append(new BigDecimal(c).toPlainString());
            afterWrite();
            return this;
        }

        public FastOutput println(double c) {
            return append(c).println();
        }

        public FastOutput println() {
            return append('\n');
        }

        public FastOutput flush() {
            try {
//            boolean success = false;
//            if (stringBuilderValueField != null) {
//                try {
//                    char[] value = (char[]) stringBuilderValueField.get(cache);
//                    os.write(value, 0, cache.length());
//                    success = true;
//                } catch (Exception e) {
//                }
//            }
//            if (!success) {
                os.append(cache);
//            }
                os.flush();
                cache.setLength(0);
            } catch (IOException e) {
                throw new UncheckedIOException(e);
            }
            return this;
        }

        public void close() {
            flush();
            try {
                os.close();
            } catch (IOException e) {
                throw new UncheckedIOException(e);
            }
        }

        public String toString() {
            return cache.toString();
        }

    }

    static class FastInput {
        private final InputStream is;
        private byte[] buf = new byte[1 << 13];
        private int bufLen;
        private int bufOffset;
        private int next;

        public FastInput(InputStream is) {
            this.is = is;
        }

        public void populate(int[] data) {
            for (int i = 0; i < data.length; i++) {
                data[i] = readInt();
            }
        }

        private int read() {
            while (bufLen == bufOffset) {
                bufOffset = 0;
                try {
                    bufLen = is.read(buf);
                } catch (IOException e) {
                    bufLen = -1;
                }
                if (bufLen == -1) {
                    return -1;
                }
            }
            return buf[bufOffset++];
        }

        public void skipBlank() {
            while (next >= 0 && next <= 32) {
                next = read();
            }
        }

        public int ri() {
            return readInt();
        }

        public int[] ri(int n) {
            int[] ans = new int[n];
            populate(ans);
            return ans;
        }

        public int readInt() {
            int sign = 1;

            skipBlank();
            if (next == '+' || next == '-') {
                sign = next == '+' ? 1 : -1;
                next = read();
            }

            int val = 0;
            if (sign == 1) {
                while (next >= '0' && next <= '9') {
                    val = val * 10 + next - '0';
                    next = read();
                }
            } else {
                while (next >= '0' && next <= '9') {
                    val = val * 10 - next + '0';
                    next = read();
                }
            }

            return val;
        }

    }

    static class RangeTree {
        private long[][] data;
        private static int bitShift = 6;
        private static int bitShiftValue = 1 << bitShift;
        private static int bitShiftValueMask = bitShiftValue - 1;
        private int size;
        private int n;

        private int calcLevel(int n) {
            int level = 0;
            while (n > 64) {
                level++;
                n = (n + 63) / 64;
            }
            level++;
            return level;
        }

        public RangeTree(int n) {
            this.n = n;
            int level = calcLevel(n);
            data = new long[level][];
            for (int i = 0, m = (n + 63) / 64; i < level; i++, m = (m + 63) / 64) {
                data[i] = new long[m];
            }
        }

        public boolean contains(int x) {
            return ((data[0][x >> bitShift] >>> (x & bitShiftValueMask)) & 1) == 1;
        }

        public void add(int x) {
            if (contains(x)) {
                return;
            }
            size++;
            for (int i = 0; i < data.length; i++) {
                int offset = x & bitShiftValueMask;
                x >>= bitShift;
                data[i][x] = Bits.set(data[i][x], offset);
            }
        }

        private int lastSet(int i, int x) {
            assert i < 0 || data[i][x] != 0;
            for (; i >= 0; i--) {
                int offset = Bits.highestOneBitOffset(data[i][x]);
                x = (x << bitShift) | offset;
            }
            return x;
        }

        private int firstSet(int i, int x) {
            assert i < 0 || data[i][x] != 0;
            for (; i >= 0; i--) {
                int offset = Bits.lowestOneBitOffset(data[i][x]);
                x = (x << bitShift) | offset;
            }
            return x;
        }

        public int floor(int x) {
            if (x < 0) {
                return -1;
            }
            if (contains(x)) {
                return x;
            }
            for (int i = 0, y = x; i < data.length; i++) {
                int offset = y & bitShiftValueMask;
                y = y >>> bitShift;
                long headMask = Bits.headMask(offset);
                if ((data[i][y] & headMask) != 0) {
                    return lastSet(i - 1, (y << bitShift) | Bits.highestOneBitOffset(data[i][y] & headMask));
                }
            }
            return -1;
        }

        public int ceil(int x) {
            if (x >= n) {
                return -1;
            }
            if (contains(x)) {
                return x;
            }
            for (int i = 0, y = x; i < data.length; i++) {
                int offset = y & bitShiftValueMask;
                y = y >>> bitShift;
                long tailMask = Bits.tailMask(63 - offset);
                if ((data[i][y] & tailMask) != 0) {
                    return firstSet(i - 1, (y << bitShift) | Bits.lowestOneBitOffset(data[i][y] & tailMask));
                }
            }
            return -1;
        }

        public IntegerIterator iterator() {
            return iterator(0, n - 1);
        }

        public IntegerIterator iterator(int l, int r) {
            return new IntegerIterator() {
                int cur = ceil(l);


                public boolean hasNext() {
                    return cur <= r && cur != -1;
                }


                public int next() {
                    int ans = cur;
                    if (cur == r) {
                        cur = -1;
                    } else {
                        cur = ceil(cur + 1);
                    }
                    assert cur == -1 || cur > ans;
                    return ans;
                }
            };
        }

        public String toString() {
            IntegerIterator iterator = iterator();
            List<Integer> list = new ArrayList<>(n);
            for (; iterator.hasNext(); ) {
                list.add(iterator.next());
            }
            return list.toString();
        }

    }

    static class SortUtils {
        private static final int THRESHOLD = 8;

        private SortUtils() {
        }

        public static void insertSort(int[] data, IntegerComparator cmp, int l, int r) {
            for (int i = l + 1; i <= r; i++) {
                int j = i;
                int val = data[i];
                while (j > l && cmp.compare(data[j - 1], val) > 0) {
                    data[j] = data[j - 1];
                    j--;
                }
                data[j] = val;
            }
        }

        public static void quickSort(int[] data, IntegerComparator cmp, int f, int t) {
            if (t - f <= THRESHOLD) {
                insertSort(data, cmp, f, t - 1);
                return;
            }
            SequenceUtils.swap(data, f, RandomWrapper.INSTANCE.nextInt(f, t - 1));
            int l = f;
            int r = t;
            int m = l + 1;
            while (m < r) {
                int c = cmp.compare(data[m], data[l]);
                if (c == 0) {
                    m++;
                } else if (c < 0) {
                    SequenceUtils.swap(data, l, m);
                    l++;
                    m++;
                } else {
                    SequenceUtils.swap(data, m, --r);
                }
            }
            quickSort(data, cmp, f, l);
            quickSort(data, cmp, m, t);
        }

    }
}