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 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_, _p_1, _p_2, ..., _p__k_. All _k_! permutation are equiprobable.
3. This permutation is applied to elements of the chosen segment, i.e. permutation _a_1, _a_2, ..., _a__l_ - 1, _a__l_, _a__l_ + 1, ..., _a__r_ - 1, _a__r_, _a__r_ + 1, ..., _a__n_ is transformed to _a_1, _a_2, ..., _a__l_ - 1, _a__l_ - 1 + _p_1, _a__l_ - 1 + _p_2, ..., _a__l_ - 1 + _p__k_ - 1, _a__l_ - 1 + _p__k_, _a__r_ + 1, ..., _a__n_.
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 _a__i_ > _a__j_. 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 .
[samples]
给定一个从 #cf_span[1] 到 #cf_span[n] 的整数排列。你恰好应用一次以下操作到该排列：随机选择一个区间并打乱其元素。形式化地：
#cf_span(class=[tex-font-style-underline], body=[Inversion]) 指一对元素（不一定是相邻的）具有错误的相对顺序。换句话说，逆序对的数量等于满足 #cf_span[i < j] 且 #cf_span[ai > aj] 的对 #cf_span[(i, j)] 的数量。求应用上述操作后逆序对的期望数量。
第一行包含一个整数 #cf_span[n] (#cf_span[1 ≤ n ≤ 100 000]) —— 排列的长度。
第二行包含 #cf_span[n] 个从 #cf_span[1] 到 #cf_span[n] 的不同整数 —— 排列的元素。
请输出一个实数 —— 逆序对的期望数量。你的答案若绝对误差或相对误差不超过 #cf_span[10 - 9]，则被视为正确。
具体而言：设你的答案为 #cf_span[a]，评测标准答案为 #cf_span[b]。评测程序将认为你的答案正确，当且仅当 。
## Input
第一行包含一个整数 #cf_span[n] (#cf_span[1 ≤ n ≤ 100 000]) —— 排列的长度。第二行包含 #cf_span[n] 个从 #cf_span[1] 到 #cf_span[n] 的不同整数 —— 排列的元素。
## Output
请输出一个实数 —— 逆序对的期望数量。你的答案若绝对误差或相对误差不超过 #cf_span[10 - 9]，则被视为正确。具体而言：设你的答案为 #cf_span[a]，评测标准答案为 #cf_span[b]。评测程序将认为你的答案正确，当且仅当 。
[samples]
**Definitions**
Let $ n \in \mathbb{Z}^+ $ be the length of the permutation.
Let $ \pi = (\pi_1, \pi_2, \dots, \pi_n) $ be a given permutation of $ \{1, 2, \dots, n\} $.
Let $ \mathcal{S} $ be the set of all contiguous subarrays (segments) of $ \pi $, i.e., $ \mathcal{S} = \{ [l, r] \mid 1 \leq l \leq r \leq n \} $.
Let $ \mathcal{U} $ be the uniform distribution over $ \mathcal{S} $: each segment $ [l, r] \in \mathcal{S} $ is chosen with probability $ \frac{1}{|\mathcal{S}|} = \frac{2}{n(n+1)} $.
Given a segment $ [l, r] $, let $ \pi' $ be the permutation obtained by shuffling $ \pi_l, \pi_{l+1}, \dots, \pi_r $ uniformly at random (i.e., replacing the subsequence with a uniformly random permutation of those elements), while keeping the rest unchanged.
Let $ I(\pi) $ denote the number of inversions in permutation $ \pi $:
$$
I(\pi) = \sum_{1 \leq i < j \leq n} \mathbf{1}_{\pi_i > \pi_j}
$$
Let $ \mathbb{E}[I(\pi')] $ denote the expected number of inversions after applying one random segment shuffle.
**Constraints**
1. $ 1 \leq n \leq 100{,}000 $
2. $ \pi $ is a permutation of $ \{1, 2, \dots, n\} $
**Objective**
Compute
$$
\mathbb{E}[I(\pi')] = \sum_{[l,r] \in \mathcal{S}} \frac{1}{|\mathcal{S}|} \cdot \mathbb{E}[I(\pi'_{l,r})]
$$
where $ \pi'_{l,r} $ is the permutation after shuffling segment $ [l, r] $.