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 CPP):

Solution:
#include <bits/stdc++.h>
#pragma GCC optimize("Ofast")
#pragma GCC target("sse3", "sse2", "sse")
#pragma GCC target("avx", "sse4", "sse4.1", "sse4.2", "ssse3")
#pragma GCC target("f16c")
#pragma GCC optimize("inline", "fast-math", "unroll-loops", \
                     "no-stack-protector")
using namespace std;
template <typename Iter>
ostream& _out(ostream& s, Iter b, Iter e) {
  s << "[";
  for (auto it = b; it != e; it++) s << (it == b ? "" : " ") << *it;
  s << "]";
  return s;
}
template <class T1, class T2>
ostream& operator<<(ostream& out, pair<T1, T2> p) {
  return out << '(' << p.first << ", " << p.second << ')';
}
template <class T1, class T2>
istream& operator>>(istream& in, pair<T1, T2>& p) {
  return in >> p.first >> p.second;
}
template <typename T>
ostream& operator<<(ostream& s, const vector<T>& c) {
  return _out(s, c.begin(), c.end());
}
template <typename T, size_t N>
ostream& operator<<(ostream& s, const array<T, N>& c) {
  return _out(s, c.begin(), c.end());
}
inline char readchar() {
  const int64_t S = 1 << 20;
  static char buf[S], *p = buf, *q = buf;
  if (p == q && (q = (p = buf) + fread(buf, 1, S, stdin)) == buf) return EOF;
  return *p++;
}
inline void input(int64_t& _x) {
  _x = 0;
  int64_t _tmp = 1;
  char _tc = readchar();
  while (_tc < '0' || _tc > '9') _tc = readchar();
  while (_tc >= '0' && _tc <= '9')
    _x = (_x << 1) + (_x << 3) + (_tc - 48), _tc = readchar();
}
inline void output(int64_t _x) {
  char _buff[20];
  int64_t _f = 0;
  if (_x == 0) putchar('0');
  while (_x > 0) {
    _buff[_f++] = _x % 10 + '0';
    _x /= 10;
  }
  for (_f -= 1; _f >= 0; _f--) putchar(_buff[_f]);
  putchar('\n');
}
struct Q {
  long double man = 1;
  int64_t ex = 0;
  Q(long double i, int64_t j = 0) {
    assert(abs(i) <= 1e-7 || i >= 1 - 1e-7);
    man = i, ex += j;
  }
  friend Q operator+(const Q a, const Q b) {
    if (abs(a.man) <= 1e-7) return b;
    if (abs(b.man) <= 1e-7) return a;
    return Q(a.man * pow(0.5, a.ex - min(a.ex, b.ex)) +
                 b.man * pow(0.5, b.ex - min(a.ex, b.ex)),
             min(a.ex, b.ex));
  }
  friend Q operator*(const Q a, const Q b) {
    return Q(a.man * b.man, a.ex + b.ex);
  }
  operator long double() { return man * pow(0.5, ex); }
};
struct node {
  node *L, *R;
  int64_t l, r, mid;
  Q sum = 1;
  int64_t lt = 0;
  node(int64_t a, int64_t b) {
    l = a, r = b, mid = l + r >> 1;
    if (l != r) L = new node(l, mid), R = new node(mid + 1, r), up();
  }
  void upd(int64_t x) { lt += x, sum.ex += x; }
  void down() { L->upd(lt), R->upd(lt), lt = 0; }
  void up() { sum = L->sum + R->sum; }
  void update(int64_t ll, int64_t rr) {
    if (ll <= l && rr >= r) return upd(1);
    if (ll > r || rr < l) return;
    down();
    L->update(ll, rr);
    R->update(ll, rr);
    up();
  }
  Q query(int64_t ll, int64_t rr) {
    if (ll <= l && rr >= r) return sum;
    if (ll > r || rr < l) return 0;
    down();
    return L->query(ll, rr) + R->query(ll, rr);
  }
  int64_t getLT(int64_t i) {
    if (l == r) return lt;
    return down(), (i <= mid ? L : R)->getLT(i);
  }
} * rootl, *rootr;
vector<int64_t> v;
vector<pair<int64_t, int64_t> > evts;
signed main() {
  cin.tie(0);
  cout.tie(0);
  ios::sync_with_stdio(0);
  ;
  int64_t n;
  cin >> n;
  v.resize(n + 1);
  for (int64_t i = 1; i <= n; i++) cin >> v[i], evts.push_back({v[i], i});
  rootl = new node(1, n);
  rootr = new node(1, n);
  sort((evts).begin(), (evts).end());
  reverse((evts).begin(), (evts).end());
  long double ans = 0;
  for (auto [x, pos] : evts) {
    ans += rootl->query(1, pos) * rootr->query(pos, n) *
           Q(1, -rootl->getLT(pos) - rootr->getLT(pos) + 1) / n / n * x;
    rootl->update(1, pos), rootr->update(pos, n);
  }
  cout << setprecision(20) << fixed << ans << endl;
}