{"problem":{"name":"E. Inversions After Shuffle","description":{"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: 1.  Pick a random ","description_type":"Markdown"},"platform":"Codeforces","limit":{"time_limit":1000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"CF749E"},"statements":[{"statement_type":"Markdown","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.\n\n## Input\n\nThe 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.\n\n## Output\n\nPrint 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 .\n\n[samples]","is_translate":false,"language":"English"},{"statement_type":"Markdown","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## Input\n\n第一行包含一个整数 #cf_span[n] (#cf_span[1 ≤ n ≤ 100 000]) —— 排列的长度。第二行包含 #cf_span[n] 个从 #cf_span[1] 到 #cf_span[n] 的不同整数 —— 排列的元素。\n\n## Output\n\n请输出一个实数 —— 逆序对的期望数量。你的答案若绝对误差或相对误差不超过 #cf_span[10 - 9]，则被视为正确。具体而言：设你的答案为 #cf_span[a]，评测标准答案为 #cf_span[b]。评测程序将认为你的答案正确，当且仅当 。\n\n[samples]","is_translate":true,"language":"Chinese"},{"statement_type":"Markdown","content":"**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] $.","is_translate":false,"language":"Formal"}],"meta":{"iden":"CF749E","tags":["data structures","probabilities"],"sample_group":[["3\n2 3 1","1.916666666666666666666666666667"]],"created_at":"2026-03-03 11:00:39"}}