{"raw_statement":[{"iden":"statement","content":"You are given an array _a_ consisting of _n_ positive integers. You pick two integer numbers _l_ and _r_ from 1 to _n_, inclusive (numbers are picked randomly, equiprobably and independently). If _l_ > _r_, then you swap values of _l_ and _r_. You have to calculate the expected value of the number of unique elements in segment of the array from index _l_ to index _r_, inclusive (1\\-indexed)."},{"iden":"input","content":"The first line contains one integer number _n_ (1 ≤ _n_ ≤ 106). The second line contains _n_ integer numbers _a_1, _a_2, ... _a__n_ (1 ≤ _a__i_ ≤ 106) — elements of the array."},{"iden":"output","content":"Print one number — the expected number of unique elements in chosen segment.\n\nYour answer will be considered correct if its absolute or relative error doesn't exceed 10 - 4 — formally, the answer is correct if , where _x_ is jury's answer, and _y_ is your answer."},{"iden":"examples","content":"Input\n\n2\n1 2\n\nOutput\n\n1.500000\n\nInput\n\n2\n2 2\n\nOutput\n\n1.000000"}],"translated_statement":[{"iden":"statement","content":"给定一个包含 $n$ 个正整数的数组 $[a]$。你从 $1$ 到 $n$ 中随机、等概率且独立地选取两个整数 $l$ 和 $r$。如果 $l > r$，则交换 $l$ 和 $r$ 的值。你需要计算在数组从索引 $l$ 到索引 $r$（包含两端，$1$-索引）的子段中，不同元素个数的期望值。\n\n第一行包含一个整数 $n$ $ (1 ≤ n ≤ 10^6) $。第二行包含 $n$ 个整数 $a_1, a_2, \\dots, a_n$ $ (1 ≤ a_i ≤ 10^6) $ —— 数组的元素。\n\n输出一个数——所选子段中不同元素的期望个数。\n\n你的答案若绝对误差或相对误差不超过 $10^{-4}$，则被视为正确——形式上，当 $ \\frac{|x - y|}{\\max(1, |x|)} \\leq 10^{-4} $ 时，答案正确，其中 $x$ 是评测标准答案，$y$ 是你的答案。"},{"iden":"input","content":"第一行包含一个整数 $n$ $ (1 ≤ n ≤ 10^6) $。第二行包含 $n$ 个整数 $a_1, a_2, \\dots, a_n$ $ (1 ≤ a_i ≤ 10^6) $ —— 数组的元素。"},{"iden":"output","content":"输出一个数——所选子段中不同元素的期望个数。你的答案若绝对误差或相对误差不超过 $10^{-4}$，则被视为正确——形式上，当 $ \\frac{|x - y|}{\\max(1, |x|)} \\leq 10^{-4} $ 时，答案正确，其中 $x$ 是评测标准答案，$y$ 是你的答案。"},{"iden":"examples","content":"输入21 2输出1.500000输入22 2输出1.000000"}],"sample_group":[],"show_order":[],"formal_statement":"Let $ a = [a_1, a_2, \\dots, a_n] $ be an array of $ n $ positive integers.\n\nLet $ L, R $ be independent random variables uniformly distributed over $ \\{1, 2, \\dots, n\\} $.\n\nDefine $ \\ell = \\min(L, R) $, $ r = \\max(L, R) $.  \nLet $ S = \\{a_i \\mid \\ell \\leq i \\leq r\\} $ be the set of distinct elements in the segment $ [\\ell, r] $.\n\nWe are to compute:\n\n$$\n\\mathbb{E}[|S|]\n$$\n\nBy linearity of expectation:\n\n$$\n\\mathbb{E}[|S|] = \\sum_{j=1}^{n} \\mathbb{P}(a_j \\text{ is the first occurrence of its value in } [\\ell, r])\n$$\n\nAlternatively, equivalently:\n\n$$\n\\mathbb{E}[|S|] = \\sum_{k=1}^{n} \\mathbb{P}(\\text{the value } a_k \\text{ appears in } [\\ell, r] \\text{ and no earlier occurrence of } a_k \\text{ is in } [\\ell, r])\n$$\n\nBut a more direct and computationally tractable formulation is:\n\n$$\n\\mathbb{E}[|S|] = \\sum_{i=1}^{n} \\mathbb{P}(a_i \\text{ contributes to the count of unique elements in } [\\ell, r])\n$$\n\nAn element $ a_i $ contributes if and only if it is the **leftmost occurrence** of its value within the interval $ [\\ell, r] $. That is, if no $ j < i $ with $ a_j = a_i $ lies in $ [\\ell, r] $.\n\nLet $ \\text{prev}(i) $ be the largest index $ j < i $ such that $ a_j = a_i $, or $ 0 $ if no such index exists.\n\nThen $ a_i $ contributes to the unique count in $ [\\ell, r] $ if and only if:\n\n$$\n\\ell \\leq i \\leq r \\quad \\text{and} \\quad \\ell > \\text{prev}(i)\n$$\n\nThus,\n\n$$\n\\mathbb{E}[|S|] = \\sum_{i=1}^{n} \\mathbb{P}(\\ell \\leq i \\leq r \\text{ and } \\ell > \\text{prev}(i))\n$$\n\nSince $ \\ell = \\min(L,R) $, $ r = \\max(L,R) $, and $ L, R \\sim \\text{Uniform}\\{1,\\dots,n\\} $ independently, the pair $ (\\ell, r) $ is uniformly distributed over all unordered pairs $ \\{i,j\\} $ with $ i \\leq j $, with multiplicities:\n\n- For $ i = j $: probability $ \\frac{1}{n^2} $\n- For $ i < j $: probability $ \\frac{2}{n^2} $\n\nThere are $ \\binom{n}{2} + n = \\frac{n(n+1)}{2} $ distinct intervals $ [\\ell, r] $, each occurring with probability:\n\n- $ \\frac{1}{n^2} $ if $ \\ell = r $\n- $ \\frac{2}{n^2} $ if $ \\ell < r $\n\nThus, we can compute:\n\n$$\n\\mathbb{E}[|S|] = \\sum_{1 \\leq \\ell \\leq r \\leq n} \\frac{w_{\\ell,r}}{n^2} \\cdot |\\{a_i : \\ell \\leq i \\leq r \\text{ and } \\text{prev}(i) < \\ell\\}|\n$$\n\nwhere $ w_{\\ell,r} = 1 $ if $ \\ell = r $, and $ w_{\\ell,r} = 2 $ if $ \\ell < r $.\n\nBut for efficient computation, we use the linearity approach:\n\nFor each position $ i \\in [1, n] $, define:\n\n$$\np_i = \\mathbb{P}(\\ell \\leq i \\leq r \\text{ and } \\ell > \\text{prev}(i))\n$$\n\nThen:\n\n$$\n\\boxed{\\mathbb{E}[|S|] = \\sum_{i=1}^{n} p_i}\n$$\n\nNow compute $ p_i $:\n\nLet $ p = \\text{prev}(i) $. We require:\n\n- $ \\ell \\leq i \\leq r $\n- $ \\ell > p $\n\nSince $ \\ell = \\min(L,R) $, $ r = \\max(L,R) $, the condition $ \\ell \\leq i \\leq r $ and $ \\ell > p $ is equivalent to:\n\n- Both $ L $ and $ R $ are in $ [p+1, n] $\n- At least one of $ L, R $ is $ \\leq i $\n- At least one of $ L, R $ is $ \\geq i $\n\nEquivalently: the pair $ (L,R) $ must lie in the rectangle $ [p+1, n] \\times [p+1, n] $, and the interval $ [\\min(L,R), \\max(L,R)] $ must contain $ i $.\n\nWhich means:\n\n- $ \\min(L,R) \\leq i \\leq \\max(L,R) $\n- $ \\min(L,R) > p $\n\nSo:\n\nLet $ A = [p+1, n] $, the set of valid values for $ \\ell $.\n\nWe need the probability that $ \\min(L,R) \\in [p+1, i] $ and $ \\max(L,R) \\geq i $, with both $ L,R \\in A $.\n\nWe can compute:\n\nNumber of favorable $ (L,R) $ pairs:\n\n- Total pairs: $ n^2 $\n- Favorable: number of $ (L,R) \\in [1,n]^2 $ such that $ \\min(L,R) \\in [p+1, i] $, $ \\max(L,R) \\geq i $\n\nBreak into cases:\n\nCase 1: $ L = R = i $ → 1 pair\n\nCase 2: One of $ L,R $ is $ i $, the other is in $ [p+1, i-1] $ → $ 2(i - 1 - p) $ pairs\n\nCase 3: One is in $ [p+1, i-1] $, the other in $ [i+1, n] $ → $ 2(i - 1 - p)(n - i) $ pairs\n\nCase 4: Both in $ [i+1, n] $, but then $ \\min(L,R) > i $ → violates $ \\min(L,R) \\leq i $ → invalid\n\nWait — better:\n\nWe require:\n\n- $ \\min(L,R) \\in [p+1, i] $\n- $ \\max(L,R) \\geq i $\n\nSo:\n\nLet $ x = \\min(L,R) $, $ y = \\max(L,R) $, $ x \\in [p+1, i] $, $ y \\in [i, n] $, and $ x \\leq y $\n\nNumber of ordered pairs $ (L,R) $ such that $ \\min(L,R) = x $, $ \\max(L,R) = y $:\n\n- If $ x = y $: 1 pair\n- If $ x < y $: 2 pairs\n\nSo total favorable ordered pairs:\n\n$$\n\\sum_{x=p+1}^{i} \\sum_{y=i}^{n} \\mathbf{1}_{x \\leq y} \\cdot \\begin{cases} 1 & x = y \\\\ 2 & x < y \\end{cases}\n$$\n\nSplit:\n\n- When $ x = y $ and $ x \\in [p+1, i] \\cap [i, n] = \\{i\\} $ (if $ i \\geq p+1 $): 1 pair\n- When $ x < y $, $ x \\in [p+1, i-1] $, $ y \\in [i+1, n] $: number of such $ (x,y) $ is $ (i - 1 - p) \\cdot (n - i) $, each contributes 2 → $ 2(i - 1 - p)(n - i) $\n- When $ x \\in [p+1, i-1] $, $ y = i $: number of such $ x $ is $ i - 1 - p $, each gives 2 pairs (since $ x < i $) → $ 2(i - 1 - p) $\n\nSo total favorable ordered pairs:\n\n$$\n1 + 2(i - 1 - p)(n - i) + 2(i - 1 - p)\n= 1 + 2(i - 1 - p)(n - i + 1)\n$$\n\nTherefore:\n\n$$\np_i = \\frac{1 + 2(i - 1 - p)(n - i + 1)}{n^2}\n$$\n\nBut only if $ p < i $. If $ p = 0 $ (no previous occurrence), then $ p_i = \\mathbb{P}(\\ell \\leq i \\leq r) $\n\nWhich is:\n\nNumber of $ (L,R) $ such that $ \\min(L,R) \\leq i \\leq \\max(L,R) $\n\n= total pairs minus pairs where both $ < i $ or both $ > i $\n\n= $ n^2 - (i-1)^2 - (n-i)^2 $\n\n= $ n^2 - (i^2 - 2i + 1) - (n^2 - 2ni + i^2) $\n\n= $ n^2 - i^2 + 2i - 1 - n^2 + 2ni - i^2 $\n\n= $ 2ni - 2i^2 + 2i - 1 $\n\nBut this contradicts our earlier formula.\n\nActually, simpler:\n\nThe probability that interval $ [\\ell, r] $ contains $ i $ is:\n\n$$\n\\mathbb{P}(\\ell \\leq i \\leq r) = 1 - \\mathbb{P}(r < i) - \\mathbb{P}(\\ell > i)\n$$\n\n$$\n= 1 - \\left(\\frac{i-1}{n}\\right)^2 - \\left(\\frac{n-i}{n}\\right)^2\n$$\n\nSo:\n\n$$\n\\mathbb{P}(\\ell \\leq i \\leq r) = \\frac{2i(n - i + 1) - 1}{n^2}\n$$\n\nWait — standard result:\n\nNumber of ordered pairs $ (L,R) $ such that $ \\min(L,R) \\leq i \\leq \\max(L,R) $:\n\nTotal: $ n^2 $\n\nMinus: both $ < i $: $ (i-1)^2 $\n\nMinus: both $ > i $: $ (n - i)^2 $\n\nSo:\n\n$$\n\\mathbb{P}(\\ell \\leq i \\leq r) = \\frac{n^2 - (i-1)^2 - (n-i)^2}{n^2}\n= \\frac{2i(n - i + 1) - 1}{n^2}\n$$\n\nYes.\n\nNow, when there is a previous occurrence at $ p $, we require $ \\ell > p $, so:\n\n$$\np_i = \\mathbb{P}(\\ell \\leq i \\leq r \\text{ and } \\ell > p) = \\mathbb{P}(\\ell \\in [p+1, i], r \\geq i)\n$$\n\nWhich is:\n\nNumber of $ (L,R) $ with $ \\min(L,R) \\in [p+1, i] $, $ \\max(L,R) \\geq i $\n\nAs above:\n\n= $ n^2 - \\text{pairs where } \\min(L,R) \\leq p \\text{ or } \\max(L,R) < i $\n\nBut easier:\n\n= $ \\mathbb{P}(\\ell \\leq i \\leq r) - \\mathbb{P}(\\ell \\leq p \\text{ and } \\ell \\leq i \\leq r) $\n\n= $ \\mathbb{P}(\\ell \\leq i \\leq r) - \\mathbb{P}(\\ell \\leq p, r \\geq i) $\n\nNow:\n\n$ \\mathbb{P}(\\ell \\leq p, r \\geq i) = \\mathbb{P}(\\min(L,R) \\leq p, \\max(L,R) \\geq i) $\n\n= number of pairs where one $ \\leq p $, one $ \\geq i $\n\n= $ 2 \\cdot p \\cdot (n - i + 1) - \\mathbb{P}(L=R \\text{ and } L \\in [p+1, i-1]) $? No.\n\nActually:\n\nNumber of $ (L,R) $ with $ \\min \\leq p $, $ \\max \\geq i $:\n\n= total pairs minus (both > p) minus (both < i)\n\nWait — inclusion:\n\nLet $ A = \\{ (L,R) : \\min \\leq p, \\max \\geq i \\} $\n\nThis is equivalent to: at least one $ \\leq p $, and at least one $ \\geq i $\n\nSo:\n\n= total - (both > p) - (both < i) + (both > p and both < i)\n\nBut both > p and both < i → both in $ [p+1, i-1] $\n\nSo:\n\n|A| = $ n^2 - (n - p)^2 - (i - 1)^2 + (i - 1 - p)^2 $\n\nThus:\n\n$$\n\\mathbb{P}(\\ell \\leq p, r \\geq i) = \\frac{n^2 - (n - p)^2 - (i - 1)^2 + (i - 1 - p)^2}{n^2}\n$$\n\nThen:\n\n$$\np_i = \\mathbb{P}(\\ell \\leq i \\leq r) - \\mathbb{P}(\\ell \\leq p, r \\geq i)\n$$\n\nBut this is messy.\n\nBetter: direct count for $ p_i $:\n\nWe want number of $ (L,R) $ such that:\n\n- $ \\min(L,R) \\in [p+1, i] $\n- $ \\max(L,R) \\geq i $\n\nCase 1: $ \\min = \\max = k \\in [p+1, i] $ and $ k \\geq i $ → only $ k = i $: 1 pair\n\nCase 2: $ \\min = x \\in [p+1, i-1] $, $ \\max = y \\in [i, n] $, $ x < y $: number of such unordered pairs: $ (i - 1 - p) \\cdot (n - i + 1) $, each gives 2 ordered pairs → $ 2(i - 1 - p)(n - i + 1) $\n\nSo total favorable ordered pairs:\n\n$$\n1 + 2(i - 1 - p)(n - i + 1)\n$$\n\nThus:\n\n$$\n\\boxed{p_i = \\frac{1 + 2(i - 1 - \\text{prev}(i)) \\cdot (n - i + 1)}{n^2}}\n$$\n\nIf $ \\text{prev}(i) = 0 $, then $ p_i = \\frac{1 + 2(i - 1)(n - i + 1)}{n^2} $\n\nBut note: when $ \\text{prev}(i) = 0 $, the formula becomes:\n\n$$\np_i = \\frac{1 + 2(i-1)(n - i + 1)}{n^2}\n$$\n\nWhich matches the probability that $ [\\ell, r] $ contains $ i $, since if no previous occurrence, then whenever $ i $ is in the interval, it contributes.\n\nAnd indeed, $ \\mathbb{P}(\\ell \\leq i \\leq r) = \\frac{2i(n - i + 1) - 1}{n^2} $\n\nWait: $ 2(i-1)(n - i + 1) + 1 = 2(i-1)(n-i+1) + 1 $\n\nExpand: $ 2(i-1)(n-i+1) = 2[(i-1)(n+1) - (i-1)i] $\n\nBut numerically: for $ i=1 $, prev=0:\n\np_i = [1 + 2(0)(n)] / n^2 = 1/n^2\n\nBut $ \\mathbb{P}(\\ell \\leq 1 \\leq r) = \\mathbb{P}(1 \\in [\\ell,r]) = \\mathbb{P}(L=1 \\text{ or } R=1) = 1 - \\mathbb{P}(L \\geq 2, R \\geq 2) = 1 - ((n-1)/n)^2 = \\frac{2n-1}{n^2} $\n\nBut our formula gives 1/n^2 — contradiction.\n\nSo our formula is wrong.\n\nLet’s recast.\n\nWe want: $ \\mathbb{P}(\\ell \\leq i \\leq r \\text{ and } \\ell > p) $\n\nThis is equal to: $ \\mathbb{P}( \\min(L,R) > p \\text{ and } \\min(L,R) \\leq i \\leq \\max(L,R) ) $\n\n= $ \\mathbb{P}( \\min(L,R) \\in [p+1, i] \\text{ and } \\max(L,R) \\geq i ) $\n\nLet’s compute the number of ordered pairs $ (L,R) $ satisfying this.\n\nLet $ A = [p+1, i] $, $ B = [i, n] $\n\nWe need: $ \\min(L,R) \\in A $, $ \\max(L,R) \\in B $, and $ \\min \\leq \\max $ — always true since $ A \\subseteq [1,i] $, $ B \\subseteq [i,n] $, so $ A \\cap B = \\{i\\} $ if $ i \\geq p+1 $\n\nSo:\n\nWe count ordered pairs $ (L,R) $ such that:\n\n- $ \\min(L,R) \\in [p+1, i] $\n- $ \\max(L,R) \\geq i $\n\nThis is equivalent to:\n\n- At least one of $ L,R $ is $ \\geq i $\n- Both $ L,R $ are $ > p $\n- At least one of $ L,R $ is $ \\leq i $\n\nBut since $ \\min \\leq i $ and $ \\max \\geq i $, and both > p, then:\n\nThe set of possible values for $ L,R $ is $ [p+1, n] $\n\nWe need that the interval $ [\\min, \\max] $ contains $ i $, i.e., $ \\min \\leq i \\leq \\max $\n\nSo, among all pairs $ (L,R) \\in [p+1, n]^2 $, how many satisfy $ \\min \\leq i \\leq \\max $?\n\nTotal pairs in $ [p+1, n]^2 $: $ (n - p)^2 $\n\nNumber of pairs where both < i: $ (i - 1 - p)^2 $\n\nNumber of pairs where both > i: $ (n - i)^2 $\n\nSo number of pairs where $ \\min \\leq i \\leq \\max $ and both in $ [p+1, n] $ is:\n\n$$\n(n - p)^2 - (i - 1 - p)^2 - (n - i)^2\n$$\n\nTherefore:\n\n$$\np_i = \\frac{(n - p)^2 - (i - 1 - p)^2 - (n - i)^2}{n^2}\n$$\n\nSimplify numerator:\n\nLet $ a = n - p $, $ b = i - 1 - p $, $ c = n - i $\n\nThen: $ a^2 - b^2 - c^2 $\n\nBut $ a = (n - i) + (i - p) = c + (i - p) $\n\nAnd $ b = i - 1 - p = (i - p) - 1 $\n\nLet $ d = i - p $\n\nThen:\n\nNumerator = $ (c + d)^2 - (d - 1)^2 - c^2 $\n\n= $ c^2 + 2cd + d^2 - (d^2 - 2d + 1) - c^2 $\n\n= $ 2cd + 2d - 1 $\n\n= $ 2d(c + 1) - 1 $\n\nBut $ d = i - p $, $ c = n - i $, so $ c + 1 = n - i + 1 $\n\nThus:\n\nNumerator = $ 2(i - p)(n - i + 1) - 1 $\n\nTherefore:\n\n$$\n\\boxed{p_i = \\frac{2(i - \\text{prev}(i)) \\cdot (n - i + 1) - 1}{n^2}}\n$$\n\nAnd if $ \\text{prev}(i) = 0 $, then $ p_i = \\frac{2i(n - i + 1) - 1}{n^2} $, which matches the known probability that $ i \\in [\\ell, r] $.\n\nPerfect.\n\nSo final answer:\n\n$$\n\\boxed{\\mathbb{E}[|S|] = \\sum_{i=1}^{n} \\frac{2(i - \\text{prev}(i)) \\cdot (n - i + 1) - 1}{n^2}}\n$$\n\nWhere $ \\text{prev}(i) $ is the largest index $ j < i $ such that $ a_j = a_i $, or 0 if none exists.\n\nThis can be computed in $ O(n) $ time by precomputing $ \\text{prev}(i) $ using a hash map.","simple_statement":null,"has_page_source":false}