{"raw_statement":[{"iden":"statement","content":"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:\n\n1.  Pick a random segment (continuous subsequence) from _l_ to _r_. All segments are equiprobable.\n2.  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.\n3.  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_.\n\nInversion 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."},{"iden":"input","content":"The first line contains a single integer _n_ (1 ≤ _n_ ≤ 100 000) — the length of the permutation.\n\nThe second line contains _n_ distinct integers from 1 to _n_ — elements of the permutation."},{"iden":"output","content":"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.\n\nNamely: 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 ."},{"iden":"example","content":"Input\n\n3\n2 3 1\n\nOutput\n\n1.916666666666666666666666666667"}],"translated_statement":[{"iden":"statement","content":"给定一个从 #cf_span[1] 到 #cf_span[n] 的整数排列。你恰好应用一次以下操作到该排列：随机选择一个区间并打乱其元素。形式化地：\n\n#cf_span(class=[tex-font-style-underline], body=[Inversion]) 指一对元素（不一定是相邻的）具有错误的相对顺序。换句话说，逆序对的数量等于满足 #cf_span[i < j] 且 #cf_span[ai > aj] 的对 #cf_span[(i, j)] 的数量。求应用上述操作后逆序对的期望数量。\n\n第一行包含一个整数 #cf_span[n] (#cf_span[1 ≤ n ≤ 100 000]) —— 排列的长度。\n\n第二行包含 #cf_span[n] 个从 #cf_span[1] 到 #cf_span[n] 的不同整数 —— 排列的元素。\n\n请输出一个实数 —— 逆序对的期望数量。你的答案若绝对误差或相对误差不超过 #cf_span[10 - 9]，则被视为正确。\n\n具体而言：设你的答案为 #cf_span[a]，评测标准答案为 #cf_span[b]。评测程序将认为你的答案正确，当且仅当 。\n\n"},{"iden":"input","content":"第一行包含一个整数 #cf_span[n] (#cf_span[1 ≤ n ≤ 100 000]) —— 排列的长度。第二行包含 #cf_span[n] 个从 #cf_span[1] 到 #cf_span[n] 的不同整数 —— 排列的元素。"},{"iden":"output","content":"请输出一个实数 —— 逆序对的期望数量。你的答案若绝对误差或相对误差不超过 #cf_span[10 - 9]，则被视为正确。具体而言：设你的答案为 #cf_span[a]，评测标准答案为 #cf_span[b]。评测程序将认为你的答案正确，当且仅当 。"}],"sample_group":[],"show_order":[],"formal_statement":"**Definitions**  \nLet $ n \\in \\mathbb{Z}^+ $ be the length of the permutation.  \nLet $ \\pi = (\\pi_1, \\pi_2, \\dots, \\pi_n) $ be a given permutation of $ \\{1, 2, \\dots, n\\} $.  \nLet $ \\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 \\} $.  \nLet $ \\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)} $.  \n\nGiven 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.\n\nLet $ I(\\pi) $ denote the number of inversions in permutation $ \\pi $:  \n$$\nI(\\pi) = \\sum_{1 \\leq i < j \\leq n} \\mathbf{1}_{\\pi_i > \\pi_j}\n$$\n\nLet $ \\mathbb{E}[I(\\pi')] $ denote the expected number of inversions after applying one random segment shuffle.\n\n**Constraints**  \n1. $ 1 \\leq n \\leq 100{,}000 $  \n2. $ \\pi $ is a permutation of $ \\{1, 2, \\dots, n\\} $\n\n**Objective**  \nCompute  \n$$\n\\mathbb{E}[I(\\pi')] = \\sum_{[l,r] \\in \\mathcal{S}} \\frac{1}{|\\mathcal{S}|} \\cdot \\mathbb{E}[I(\\pi'_{l,r})]\n$$  \nwhere $ \\pi'_{l,r} $ is the permutation after shuffling segment $ [l, r] $.","simple_statement":null,"has_page_source":false}