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.*;
import java.util.Random;
import java.util.StringTokenizer;

public class E {

    final boolean ONLINE_JUDGE = System.getProperty("ONLINE_JUDGE") != null;
    BufferedReader in;
    PrintWriter out;
    StringTokenizer tok = new StringTokenizer("");

    void solve() throws IOException {
        int n = readInt();
        int[] a = readArr(n);
        Treap treap = new Treap();
        double res = 0;
        long total = (n + 1) * 1l * n;
        long invCount = 0;
        for(int i = 0; i < n; i++) {
            long sum = treap.getTotal(a[i]);
            long tmp = sum * (n-i);
            res += tmp / (double) total;
            invCount += treap.getInv(a[i]);
            treap.add(a[i], i+1);
        }
        out.println(invCount + res);
    }

    class Treap {
        Random rg = new Random(122);
        Node root;

        class Node {
            int key;
            long sum;
            int value;
            long prior;
            int count;
            Node left;
            Node right;

            public Node(int key, int value) {
                this.value = value;
                this.sum = value;
                this.key = key;
                this.count = 1;
                this.prior = rg.nextLong();
            }
        }

        void add(int key, int value) {
            Node[] parts = split(root, key);
            root = merge(parts[0], merge(new Node(key, value), parts[1]));
        }

        long getTotal(int key) {
            Node[] parts = split(root, key);
            long plus = getSum(parts[0]);
            long minus = getSum(parts[1]);
            root = merge(parts[0], parts[1]);
            return plus - minus;
        }

        int getInv(int key) {
            Node[] parts = split(root, key);
            int inv = getCount(parts[1]);
            root = merge(parts[0], parts[1]);
            return inv;
        }

        long getSum(Node node) {
            return node == null ? 0 : node.sum;
        }

        int getCount(Node node) {
            return node == null ? 0 : node.count;
        }
        void update(Node node) {
            if(node != null) {
                node.sum = node.value + getSum(node.left) + getSum(node.right);
                node.count = 1 + getCount(node.left) + getCount(node.right);
            }
        }

        Node merge(Node left, Node right) {
            if(left == null) {
                return right;
            }
            if(right == null) {
                return left;
            }

            Node res;
            if(left.prior > right.prior) {
                left.right = merge(left.right, right);
                res = left;
            } else {
                right.left = merge(left, right.left);
                res = right;
            }
            update(res);
            return res;
        }

        Node[] split(Node node, int key) {
            if(node == null) return new Node[2];

            int rootKey = node.key;
            Node[] res;
            if(key < rootKey) {
                res = split(node.left, key);
                node.left = res[1];
                res[1] = node;
            } else if(key > rootKey){
                res = split(node.right, key);
                node.right = res[0];
                res[0] = node;
            } else {
                res = new Node[2];
                res[0] = node;
                res[1] = node.right;
                node.right = null;
            }

            update(res[0]);
            update(res[1]);
            return res;
        }

    }

    void init() throws FileNotFoundException {
        if (ONLINE_JUDGE) {
            in = new BufferedReader(new InputStreamReader(System.in));
            out = new PrintWriter(System.out);
        } else {
            in = new BufferedReader(new FileReader("input.txt"));
            out = new PrintWriter("output.txt");
        }
    }

    String readString() throws IOException {
        while (!tok.hasMoreTokens()) {
            tok = new StringTokenizer(in.readLine());
        }
        return tok.nextToken();
    }

    int readInt() throws IOException {
        return Integer.parseInt(readString());
    }

    long readLong() throws IOException {
        return Long.parseLong(readString());
    }

    double readDouble() throws IOException {
        return Double.parseDouble(readString());
    }

    int[] readArr(int n) throws IOException {
        int[] res = new int[n];
        for (int i = 0; i < n; i++) {
            res[i] = readInt();
        }
        return res;
    }

    long[] readArrL(int n) throws IOException {
        long[] res = new long[n];
        for (int i = 0; i < n; i++) {
            res[i] = readLong();
        }
        return res;
    }

    public static void main(String[] args) {
        new E().run();
    }

    public void run() {
        try {
            long t1 = System.currentTimeMillis();
            init();
            solve();
            out.close();
            long t2 = System.currentTimeMillis();
            System.err.println("Time = " + (t2 - t1));
        } catch (Exception e) {
            e.printStackTrace(System.err);
            System.exit(-1);
        }
    }
}