//求二叉排序树的平均查找长度
#include <bits/stdc++.h>
using namespace std;
int tree[100500]={0};
void insert(int k,int val)
{
    if(tree[k]==0)
    {
        tree[k]=val;
        return ;
    }
    if(val>tree[k])
        insert(2*k+1,val);
    else if(val<=tree[k])
        insert(2*k,val);
}
int ans=0;
void dfs(int k,int depth)
{
    if(tree[k]==0)
        return ;
    ans+=depth;
    dfs(2*k,depth+1);
    dfs(2*k+1,depth+1);
}
int main()
{
    int n,m;
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        cin>>m;
        insert(1,m);
    }
    dfs(1,1);
    printf("%.5f\n",ans*1.0/n);
}
/*
输入：
5
1 2 3 4 5
输出：
3.00000

输入：
5
3 1 2 5 4
输出：
2.20000
*/

///BF算法和KMP算法比较次数计算
#include <bits/stdc++.h>
using namespace std;
char a[100500] = {0};
char b[100500] = {0};
int next1[100500] = {0};
void get_next(char c[100500])
{
    next1[0] = -1;
    int k = -1, j = 0;
    while (c[j])
    {
        if (k == -1 || (c[j] == c[k]))
            next1[++j] = ++k;
        else
            k = next1[k];
    }
}
int main()
{
    scanf("%s%s", a, b);
    get_next(b);
    cout << "Next数组值：" << endl;
    for (int i = 0; b[i]; i++)
        cout << next1[i] << ' ';
    cout << endl;
    int i = 0, j = 0;
    int ans1 = 0, ans2 = 0;
    while (i < (int)strlen(a) && j < (int)strlen(b))
    {
        if (j == -1 || a[i] == b[j])
            i++, j++, ans1++;
        else
        {
            j = next1[j];
            if (j != -1)  ///j=-1时仅计算一次
                ans1++;
        }
    }
    for (int i = 0; a[i]; i++)
    {
        int flag = 1;
        for (int j = 0; b[j] && flag; j++)
        {
            if (a[i + j] != b[j])
                flag = 0;
            ans2++;
        }
        if (flag)
            break;
    }
    cout << "BF算法比较次数" << ans2 << endl;
    cout << "KMP算法比较次数" << ans1 << endl;
}
/*
aabcabaabbaabacaa
aaba
*/