Problem: You are given a permutation of integers from 1 to n. Exactly once you apply the following operation to this permutation: pick a random segment and shuffle its elements. Formally:

  1. Pick a random segment (continuous subsequence) from l to r. All <image> segments are equiprobable. 
  2. Let k = r - l + 1, i.e. the length of the chosen segment. Pick a random permutation of integers from 1 to k, p1, p2, ..., pk. All k! permutation are equiprobable. 
  3. This permutation is applied to elements of the chosen segment, i.e. permutation a1, a2, ..., al - 1, al, al + 1, ..., ar - 1, ar, ar + 1, ..., an is transformed to a1, a2, ..., al - 1, al - 1 + p1, al - 1 + p2, ..., al - 1 + pk - 1, al - 1 + pk, ar + 1, ..., an. 



Inversion if a pair of elements (not necessary neighbouring) with the wrong relative order. In other words, the number of inversion is equal to the number of pairs (i, j) such that i < j and ai > aj. Find the expected number of inversions after we apply exactly one operation mentioned above.

Input

The first line contains a single integer n (1 ≤ n ≤ 100 000) — the length of the permutation.

The second line contains n distinct integers from 1 to n — elements of the permutation.

Output

Print one real value — the expected number of inversions. Your answer will be considered correct if its absolute or relative error does not exceed 10 - 9. 

Namely: let's assume that your answer is a, and the answer of the jury is b. The checker program will consider your answer correct, if <image>.

Example

Input

3
2 3 1


Output

1.916666666666666666666666666667

Solution (in JAVA):

Solution:
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.util.Arrays;
import java.util.Locale;
import java.util.StringTokenizer;
 
public class InversionsDoubles {
    private void solve() throws IOException {
        int n = readInt();
        int[] p = new int[n];
        for (int i = 0; i < n; i++) {
            p[i] = readInt() - 1;
        }
 
        long inversions = 0;
        FenwickTree invTree = new FenwickTree(n);
        for (int i = n - 1; i >= 0; i--) {
            inversions += invTree.sum(p[i]);
            invTree.add(p[i], 1);
        }
 
        double mult = 1.0 / n / (n + 1); // 2.0 instead of 1.0 for reverse
        double add = 0;
        double sub = 0;
        FenwickTree sumTree = new FenwickTree(n);
        for (int i = n - 1; i >= 0; i--) {
            add += sumTree.sum(p[i], n - 1) * mult * (i + 1);
            sub += sumTree.sum(p[i]) * mult * (i + 1);
            sumTree.add(p[i], n - i);
        }
 
        double ans = inversions + add - sub;
 
        out.printf(Locale.US, "%.15f\n", ans);
    }
 
    private static class FenwickTree {
        private int n;
        private long[] t;
 
        private FenwickTree(int n) {
            this.n = n;
            this.t = new long[n + 1];
        }
 
        private void add(int i, long d) {
            i++;
            while (i <= n) {
                t[i] += d;
                i += Integer.lowestOneBit(i);
            }
        }
 
        private long sum(int r) {
            r++;
            long ans = 0;
            while (r > 0) {
                ans += t[r];
                r -= Integer.lowestOneBit(r);
            }
            return ans;
        }
 
        private long sum(int l, int r) {
            return sum(r) - sum(l - 1);
        }
 
        @Override
        public String toString() {
            long[] s = new long[n];
            for (int i = 0; i < n; i++) {
                s[i] = sum(i, i);
            }
            return Arrays.toString(s);
        }
    }
 
    //------------------------------------------------------------------------------
    public static void main(String[] args) {
        new InversionsDoubles().run();
    }
 
    private void run() {
        try {
            initIO();
            solve();
            in.close();
            out.close();
        } catch (Throwable e) {
            throw new RuntimeException(e);
        }
    }
 
    private BufferedReader in;
    private StringTokenizer tok;
    private PrintWriter out;
 
    private void initIO() throws IOException {
        in = new BufferedReader(new InputStreamReader(System.in));
        out = new PrintWriter(System.out);
//        in = new BufferedReader(new FileReader(new File("input.txt")));
//        out = new PrintWriter(new File("output.txt"));
    }
 
    private String readString() throws IOException {
        while (tok == null || !tok.hasMoreTokens()) {
            tok = new StringTokenizer(in.readLine());
        }
        return tok.nextToken();
    }
 
    @SuppressWarnings("unused")
    private int readInt() throws IOException {
        return Integer.parseInt(readString());
    }
 
    @SuppressWarnings("unused")
    private long readLong() throws IOException {
        return Integer.parseInt(readString());
    }
 
    @SuppressWarnings("unused")
    private double readDouble() throws IOException {
        return Double.parseDouble(readString());
    }
}