#include<bits/stdc++.h> using namespace std; #define int long long #define pii pair<int,int> #define fr first #define sc second #define mk make_pair #define lson t[now].ls #define rson t[now].rs const int MAXN=1000010,N=32,inf=1000000000; int n,a[MAXN],b[MAXN],f[N+5][MAXN],lg2[MAXN]; int qry(int l,int r){ if(l<1||r>n)return -1; int g=lg2[r-l+1]; return max(f[g][l],f[g][r-(1<<g)+1]); } int l[MAXN],r[MAXN],ll,rr; double jc[MAXN],ans; pair<int,int>A[MAXN]; int nex[MAXN],lst[MAXN]; int fidl(int x){ if(lst[x]==x)return x; return lst[x]=fidl(lst[x]); } int fidr(int x){ if(nex[x]==x)return x; return nex[x]=fidr(nex[x]); } void slv(){ scanf("%lld",&n); jc[0]=1;jc[1]=0.5; for(int i=2;i<=MAXN-5;i++)lg2[i]=lg2[i>>1]+1,jc[i]=jc[i-1]/2; for(int i=1;i<=n;i++){ scanf("%lld",&a[i]); nex[i]=lst[i]=i; f[0][i]=a[i];A[i]=mk(a[i],i); } for(int i=1;1<<i<=n;i++){ for(int j=1;j<=n;j++){ f[i][j]=max(f[i-1][j],f[i-1][j+(1<<i-1)]); } } sort(A+1,A+n+1); for(int I=1;I<=n;I++){int i=A[I].sc; cout<<i<<":"<<endl; int L=i,R=i;ll=rr=0; l[0]=r[0]=i; double LL=0,RR=0; for(int j=1;j<=30;j++){ int tmp=fidl(L)-1; LL+=(tmp-L)*jc[j]; cout<<tmp<<" "; L=tmp; if(L<1)break; }cout<<endl; for(int j=1;j<=30;j++){ int tmp=fidr(R)+1; RR+=(R-tmp)*jc[j]; R=tmp; cout<<tmp<<" "; if(R>n)break; }cout<<endl; ans+=a[i]*2*LL*RR; nex[i-1]=i;lst[i+1]=i; } printf("%.5f",ans/n/n); } signed main(){ slv(); return 0; }