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.OutputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.OutputStream;
import java.io.PrintWriter;
import java.util.Arrays;
import java.io.BufferedWriter;
import java.io.Writer;
import java.io.OutputStreamWriter;
import java.io.InputStream;

/**
 * Built using CHelper plug-in
 * Actual solution is at the top
 *
 * @author Jialin Ouyang (Jialin.Ouyang@gmail.com)
 */
public class Main {
  public static void main(String[] args) {
    InputStream inputStream = System.in;
    OutputStream outputStream = System.out;
    QuickScanner in = new QuickScanner(inputStream);
    QuickWriter out = new QuickWriter(outputStream);
    TaskE solver = new TaskE();
    solver.solve(1, in, out);
    out.close();
  }

  static class TaskE {
    int n;
    int[] perm;
    IntAddBinaryIndexedTree markBit;
    LongAddBinaryIndexedTree cntBit;

    public void solve(int testNumber, QuickScanner in, QuickWriter out) {
      n = in.nextInt();
      perm = in.nextInt(n);
      IntArrayUtils.update(perm, -1);
      markBit = new IntAddBinaryIndexedTree(n);
      cntBit = new LongAddBinaryIndexedTree(n);
      long invCnt = 0;
      double allInvCnt = 0;
      for (int i = n - 1; i >= 0; --i) {
        int p = perm[i];
        invCnt += markBit.calc(p);
        allInvCnt += cntBit.calc(p) * (i + 1);
        markBit.update(p, 1);
        cntBit.update(p, n - i);
      }
      double rangeCnt = n / 2. * (n + 1);
      double incInv = (n - 1.) * (n + 2) / 24;
      out.printf("%.30f\n", invCnt - allInvCnt / rangeCnt + incInv);
    }

  }

  static class QuickWriter {
    private final PrintWriter writer;

    public QuickWriter(OutputStream outputStream) {
      this.writer = new PrintWriter(new BufferedWriter(new OutputStreamWriter(outputStream)));
    }

    public QuickWriter(Writer writer) {
      this.writer = new PrintWriter(writer);
    }

    public void printf(String format, Object... objects) {
      writer.printf(format, objects);
    }

    public void close() {
      writer.close();
    }

  }

  static class LongAddBinaryIndexedTree extends AbstractLongBinaryIndexedTree {
    public LongAddBinaryIndexedTree(int capacity) {
      super(capacity);
      init(capacity);
    }


    public long merge(long x, long y) {
      return x + y;
    }


    public void init(int n, long initValue) {
      throw new UnsupportedOperationException();
    }


    public long calc(int idx, long initValue) {
      throw new UnsupportedOperationException();
    }

    public void init(int n) {
      super.init(n, 0);
    }

    public long calc(int idx) {
      return super.calc(idx, 0);
    }

  }

  static abstract class AbstractLongBinaryIndexedTree {
    private int n;
    private long[] values;

    public AbstractLongBinaryIndexedTree(int capacity) {
      values = new long[capacity];
    }

    public abstract long merge(long x, long y);

    public void init(int n, long initValue) {
      this.n = n;
      Arrays.fill(values, 0, n, initValue);
    }

    public void update(int idx, long value) {
      for (; idx < n; idx |= idx + 1) {
        values[idx] = merge(values[idx], value);
      }
    }

    public long calc(int idx, long initValue) {
      long res = initValue;
      for (; idx >= 0; idx = (idx & (idx + 1)) - 1) {
        res = merge(res, values[idx]);
      }
      return res;
    }

  }

  static class QuickScanner {
    private static final int BUFFER_SIZE = 1024;
    private InputStream stream;
    private byte[] buffer;
    private int currentPosition;
    private int numberOfChars;

    public QuickScanner(InputStream stream) {
      this.stream = stream;
      this.buffer = new byte[BUFFER_SIZE];
      this.currentPosition = 0;
      this.numberOfChars = 0;
    }

    public int nextInt() {
      int c = nextNonSpaceChar();
      boolean positive = true;
      if (c == '-') {
        positive = false;
        c = nextChar();
      }
      int res = 0;
      do {
        if (c < '0' || '9' < c) throw new RuntimeException();
        res = res * 10 + c - '0';
        c = nextChar();
      } while (!isSpaceChar(c));
      return positive ? res : -res;
    }

    public int[] nextInt(int n) {
      int[] res = new int[n];
      nextInt(n, res);
      return res;
    }

    public void nextInt(int n, int[] res) {
      for (int i = 0; i < n; ++i) {
        res[i] = nextInt();
      }
    }

    public int nextNonSpaceChar() {
      int res = nextChar();
      for (; isSpaceChar(res) || res < 0; res = nextChar()) ;
      return res;
    }

    public int nextChar() {
      if (numberOfChars == -1) {
        throw new RuntimeException();
      }
      if (currentPosition >= numberOfChars) {
        currentPosition = 0;
        try {
          numberOfChars = stream.read(buffer);
        } catch (Exception e) {
          throw new RuntimeException(e);
        }
        if (numberOfChars <= 0) {
          return -1;
        }
      }
      return buffer[currentPosition++];
    }

    public boolean isSpaceChar(int c) {
      return c == ' ' || c == '\t' || isEndOfLineChar(c);
    }

    public boolean isEndOfLineChar(int c) {
      return c == '\n' || c == '\r' || c < 0;
    }

  }

  static class IntAddBinaryIndexedTree extends AbstractIntBinaryIndexedTree {
    public IntAddBinaryIndexedTree(int capacity) {
      super(capacity);
      init(capacity);
    }


    public int merge(int x, int y) {
      return x + y;
    }


    public void init(int n, int initValue) {
      throw new UnsupportedOperationException();
    }


    public int calc(int idx, int initValue) {
      throw new UnsupportedOperationException();
    }

    public void init(int n) {
      super.init(n, 0);
    }

    public int calc(int idx) {
      return super.calc(idx, 0);
    }

  }

  static abstract class AbstractIntBinaryIndexedTree {
    private int n;
    private int[] values;

    public AbstractIntBinaryIndexedTree(int capacity) {
      values = new int[capacity];
    }

    public abstract int merge(int x, int y);

    public void init(int n, int initValue) {
      this.n = n;
      Arrays.fill(values, 0, n, initValue);
    }

    public void update(int idx, int value) {
      for (; idx < n; idx |= idx + 1) {
        values[idx] = merge(values[idx], value);
      }
    }

    public int calc(int idx, int initValue) {
      int res = initValue;
      for (; idx >= 0; idx = (idx & (idx + 1)) - 1) {
        res = merge(res, values[idx]);
      }
      return res;
    }

  }

  static class IntArrayUtils {
    public static void update(int[] values, int delta) {
      update(values, 0, values.length, delta);
    }

    public static void update(int[] values, int fromIdx, int toIdx, int delta) {
      for (int i = fromIdx; i < toIdx; ++i) {
        values[i] += delta;
      }
    }

  }
}