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.PrintStream;
import java.util.Locale;
import java.util.StringTokenizer;

public class Solution implements Runnable {
	
	private PrintStream out;
	private BufferedReader in;
	private StringTokenizer st;
	
	public void solve() throws IOException {
		int n = nextInt();
		int[] a = new int[n];
		for (int i = 0; i < n; i++) {
			a[i] = nextInt() - 1;
		}
		SegmentTree posTree = new SegmentTree(n);
		SegmentTree cntTree = new SegmentTree(n);
		double result = 0;
		double add = 0;
		double mult = 2.0 / (1.0 * n * (n + 1));
		for (int i = 0; i < n; i++) {
			posTree.set(a[i], i);
			cntTree.set(a[i], 1);
			long rpos = posTree.sum(a[i] + 1, n);
			long rcnt = cntTree.sum(a[i] + 1, n);
			
			result += rcnt;
			
			double sub = 1L * (rpos + rcnt) * (n - i);
			add = add + 0.25 * (i + 1) * i;
			result -= sub * mult;
			result += add * mult;
		}
		out.println(result);
	}
	
	public static class SegmentTree {
		private long[] a;
		private int base;
		public SegmentTree(int n) {
			base = 1;
			while (base < n) {
				base *= 2;
			}
			a = new long[base + n];
		}
		public long sum(int l, int r) {
			if (r <= l) {
				return 0;
			}
			l += base;
			r += base;
			long result = a[l];
			while (l + 1 < r) {
				if (l % 2 == 0) {
					result += a[l + 1];
				}
				if (r % 2 == 1) {
					result += a[r - 1];
				}
				l = l / 2;
				r = r / 2;
			}
			return result;
		}
		public void set(int x, long v) {
			x += base;
			a[x] = v;
			while (x > 1) {
				x = x / 2;
				a[x] = a[x * 2];
				if (x * 2 + 1 < a.length) {
					a[x] += a[x * 2 + 1];
				}
			}
		}
	}
	
	public double nextDouble() throws IOException {
		return Double.parseDouble(next());
	}
	
	public long nextLong() throws IOException {
		return Long.parseLong(next());
	}
	
	public int nextInt() throws IOException {
		return Integer.parseInt(next());
	}
	
	public String next() throws IOException {
		while (!st.hasMoreTokens()) {
			String line = in.readLine();
			if (line == null) {
				return null;
			}
			st = new StringTokenizer(line);
		}
		return st.nextToken();
	}
	
	@Override
	public void run() {
		try {
			solve();
			out.close();
		} catch (Throwable e) {
			throw new RuntimeException(e);
		}
	}
	
	public Solution() {
		out = System.out;
		in = new BufferedReader(new InputStreamReader(System.in));
		st = new StringTokenizer("");
	}
	
	public static void main(String[] args) {
		Locale.setDefault(Locale.US);
		new Thread(new Solution()).start();
	}
}