```go
package main

import (
	"fmt"
	"io"
	"os"
	"sort"
)

type Element struct {
	val int
	idx int
}

var (
	cnt   []int
	sum_L []float64
	sum_R []float64
	pow2  []float64
)

func build(u, l, r int) {
	if l == r {
		cnt[u] = 0
		sum_L[u] = 1.0
		sum_R[u] = 1.0
		return
	}
	mid := (l + r) / 2
	build(u*2, l, mid)
	build(u*2+1, mid+1, r)
	pushUp(u)
}

func pushUp(u int) {
	left := u * 2
	right := u*2 + 1
	cnt[u] = cnt[left] + cnt[right]
	sum_L[u] = sum_L[left] + sum_L[right]*pow2[cnt[left]]
	sum_R[u] = sum_R[left]*pow2[cnt[right]] + sum_R[right]
}

func activate(u, l, r, pos int) {
	if l == r {
		cnt[u] = 1
		sum_L[u] = 0.5
		sum_R[u] = 0.5
		return
	}
	mid := (l + r) / 2
	if pos <= mid {
		activate(u*2, l, mid, pos)
	} else {
		activate(u*2+1, mid+1, r, pos)
	}
	pushUp(u)
}

func query_R(u, l, r, ql, qr int) (int, float64) {
	if ql <= l && r <= qr {
		return cnt[u], sum_R[u]
	}
	mid := (l + r) / 2
	if qr <= mid {
		return query_R(u*2, l, mid, ql, qr)
	}
	if ql > mid {
		return query_R(u*2+1, mid+1, r, ql, qr)
	}
	cnt_left, sumR_left := query_R(u*2, l, mid, ql, qr)
	cnt_right, sumR_right := query_R(u*2+1, mid+1, r, ql, qr)

	return cnt_left + cnt_right, sumR_left*pow2[cnt_right] + sumR_right
}

func query_L(u, l, r, ql, qr int) (int, float64) {
	if ql <= l && r <= qr {
		return cnt[u], sum_L[u]
	}
	mid := (l + r) / 2
	if qr <= mid {
		return query_L(u*2, l, mid, ql, qr)
	}
	if ql > mid {
		return query_L(u*2+1, mid+1, r, ql, qr)
	}
	cnt_left, sumL_left := query_L(u*2, l, mid, ql, qr)
	cnt_right, sumL_right := query_L(u*2+1, mid+1, r, ql, qr)

	return cnt_left + cnt_right, sumL_left + sumL_right*pow2[cnt_left]
}

func main() {
	input, _ := io.ReadAll(os.Stdin)
	head := 0

	nextInt := func() int {
		for head < len(input) && input[head] <= ' ' {
			head++
		}
		if head >= len(input) {
			return 0
		}
		res := 0
		for head < len(input) && input[head] > ' ' {
			res = res*10 + int(input[head]-'0')
			head++
		}
		return res
	}

	n := nextInt()
	if n == 0 {
		return
	}

	elements := make([]Element, n)
	for i := 0; i < n; i++ {
		elements[i] = Element{val: nextInt(), idx: i + 1}
	}

	sort.Slice(elements, func(i, j int) bool {
		if elements[i].val == elements[j].val {
			return elements[i].idx < elements[j].idx
		}
		return elements[i].val > elements[j].val
	})

	cnt = make([]int, 4*n+1)
	sum_L = make([]float64, 4*n+1)
	sum_R = make([]float64, 4*n+1)
	pow2 = make([]float64, n+5)

	pow2[0] = 1.0
	for i := 1; i <= n; i++ {
		pow2[i] = pow2[i-1] * 0.5
	}

	build(1, 1, n)

	pL := make([]float64, n)
	pR := make([]float64, n)
	nSq := float64(n) * float64(n)

	totalSum := 0.0
	for i := 0; i < n; {
		j := i
		for j < n && elements[j].val == elements[i].val {
			j++
		}

		for k := i; k < j; k++ {
			idx := elements[k].idx
			_, pL[k] = query_R(1, 1, n, 1, idx)
		}

		for k := i; k < j; k++ {
			idx := elements[k].idx
			activate(1, 1, n, idx)
		}

		for k := i; k < j; k++ {
			idx := elements[k].idx
			_, qL := query_L(1, 1, n, idx, n)
			pR[k] = 2.0 * qL
		}

		for k := i; k < j; k++ {
			term := float64(elements[k].val) * 0.5 * pL[k] * pR[k]
			totalSum += term / nSq
		}

		i = j
	}

	fmt.Printf("%.9f\n", totalSum)
}
```