{"problem":{"name":"C. Riverside Curio","description":{"content":"Arkady decides to observe a river for _n_ consecutive days. The river's water level on each day is equal to some real value. Arkady goes to the riverside each day and makes a mark on the side of the ","description_type":"Markdown"},"platform":"Codeforces","limit":{"time_limit":1000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"CF924C"},"statements":[{"statement_type":"Markdown","content":"Arkady decides to observe a river for _n_ consecutive days. The river's water level on each day is equal to some real value.\n\nArkady goes to the riverside each day and makes a mark on the side of the channel at the height of the water level, but if it coincides with a mark made before, no new mark is created. The water does not wash the marks away. Arkady writes down the number of marks strictly above the water level each day, on the _i_\\-th day this value is equal to _m__i_.\n\nDefine _d__i_ as the number of marks strictly under the water level on the _i_\\-th day. You are to find out the minimum possible sum of _d__i_ over all days. There are no marks on the channel before the first day.\n\n## Input\n\nThe first line contains a single positive integer _n_ (1 ≤ _n_ ≤ 105) — the number of days.\n\nThe second line contains _n_ space-separated integers _m_1, _m_2, ..., _m__n_ (0 ≤ _m__i_ < _i_) — the number of marks strictly above the water on each day.\n\n## Output\n\nOutput one single integer — the minimum possible sum of the number of marks strictly below the water level among all days.\n\n[samples]\n\n## Note\n\nIn the first example, the following figure shows an optimal case.\n\nNote that on day 3, a new mark should be created because if not, there cannot be 3 marks above water on day 4. The total number of marks underwater is 0 + 0 + 2 + 0 + 3 + 1 = 6.\n\nIn the second example, the following figure shows an optimal case.\n\n","is_translate":false,"language":"English"},{"statement_type":"Markdown","content":"[{\"iden\":\"statement\",\"content\":\"Arkady 决定连续观察一条河流 #cf_span[n] 天。每天河流的水位等于某个实数值。\\n\\nArkady 每天都会到河边，在水位高度处的渠道侧壁上做标记，但如果该高度已有标记，则不再创建新标记。水不会冲走已有的标记。Arkady 每天记录严格高于水位的标记数量，第 #cf_span[i] 天这个值为 #cf_span[mi]。\\n\\n定义 #cf_span[di] 为第 #cf_span[i] 天严格低于水位的标记数量。你需要求出所有天数中 #cf_span[di] 的最小可能总和。在第一天之前，渠道上没有任何标记。\\n\\n第一行包含一个正整数 #cf_span[n] (#cf_span[1 ≤ n ≤ 105]) —— 天数。\\n\\n第二行包含 #cf_span[n] 个空格分隔的整数 #cf_span[m1, m2, ..., mn] (#cf_span[0 ≤ mi < i]) —— 每天严格高于水位的标记数量。\\n\\n输出一个整数 —— 所有天数中严格低于水位的标记数量的最小可能总和。\\n\\n在第一个例子中，下图展示了一种最优情况。\\n\\n注意：在第 #cf_span[3] 天，必须创建一个新标记，否则第 #cf_span[4] 天不可能有 #cf_span[3] 个标记高于水位。水下标记总数为 #cf_span[0 + 0 + 2 + 0 + 3 + 1 = 6]。\\n\\n在第二个例子中，下图展示了一种最优情况。\\n\\n\"},{\"iden\":\"input\",\"content\":\"第一行包含一个正整数 #cf_span[n] (#cf_span[1 ≤ n ≤ 105]) —— 天数。第二行包含 #cf_span[n] 个空格分隔的整数 #cf_span[m1, m2, ..., mn] (#cf_span[0 ≤ mi < i]) —— 每天严格高于水位的标记数量。\"},{\"iden\":\"output\",\"content\":\"输出一个整数 —— 所有天数中严格低于水位的标记数量的最小可能总和。\"},{\"iden\":\"examples\",\"content\":\"输入60 1 0 3 0 2输出6输入50 1 2 1 2输出1输入50 1 1 2 2输出0\"},{\"iden\":\"note\",\"content\":\"在第一个例子中，下图展示了一种最优情况。注意：在第 #cf_span[3] 天，必须创建一个新标记，否则第 #cf_span[4] 天不可能有 #cf_span[3] 个标记高于水位。水下标记总数为 #cf_span[0 + 0 + 2 + 0 + 3 + 1 = 6]。在第二个例子中，下图展示了一种最优情况。 \"}]\n\n注意：根据要求，所有数学公式（如 #cf_span[n]、#cf_span[mi] 等）和 Typst 命令（如 #cf_span[...]）均保持原样未改动，仅翻译了自然语言部分。格式和换行符与原文完全一致。","is_translate":true,"language":"Chinese"},{"statement_type":"Markdown","content":"Let $ n $ be the number of days. \nLet $ m_i \\in \\mathbb{Z} $ denote the number of marks strictly **above** the water level on day $ i $, for $ i = 1, 2, \\dots, n $, with $ 0 \\leq m_i < i $.\n\nLet $ a_i $ be the total number of distinct marks present on the channel at the end of day $ i $. \nLet $ d_i $ be the number of marks strictly **below** the water level on day $ i $.\n\nOn day $ i $, the water level coincides with exactly one mark (the one made that day, or an existing one). \nThus, the total number of marks at the end of day $ i $ is: \n$$\na_i = a_{i-1} + \\delta_i, \\quad \\text{where } \\delta_i = \n\\begin{cases}\n1 & \\text{if a new mark is made on day } i, \\\\\n0 & \\text{otherwise}.\n\\end{cases}\n$$\n\nThe number of marks **above** the water on day $ i $ is $ m_i $. \nThe number of marks **below** the water on day $ i $ is $ d_i $. \nThe water level itself is at one mark, so: \n$$\na_i = m_i + d_i + 1\n\\quad \\Rightarrow \\quad\nd_i = a_i - m_i - 1.\n$$\n\nWe are to minimize $ \\sum_{i=1}^n d_i = \\sum_{i=1}^n (a_i - m_i - 1) = \\left( \\sum_{i=1}^n a_i \\right) - \\left( \\sum_{i=1}^n m_i \\right) - n $.\n\nSince $ \\sum m_i $ is fixed, minimizing $ \\sum d_i $ is equivalent to minimizing $ \\sum_{i=1}^n a_i $.\n\nWe now determine the minimal possible sequence $ \\{a_i\\} $ consistent with the constraints:\n\n- $ a_0 = 0 $ (no marks before day 1).\n- On day $ i $, there are $ m_i $ marks above the water level. \n Since marks are only added and never removed, the number of marks **above** the water level on day $ i $ cannot exceed the total number of marks made so far: \n $$\n m_i \\leq a_{i-1}.\n $$\n Why? Because the $ m_i $ marks above the water must have been made on previous days (since the current day’s mark is either at water level or below — but if it's above, then it would be counted in $ m_i $, which is impossible because the water level is at the mark made that day).\n\nActually, the mark made on day $ i $ is **at** the water level. So the $ m_i $ marks above the water must come from the previous $ a_{i-1} $ marks. \nTherefore: \n$$\nm_i \\leq a_{i-1}.\n$$\n\nAlso, if a new mark is made on day $ i $, then $ a_i = a_{i-1} + 1 $. \nIf not, $ a_i = a_{i-1} $.\n\nTo minimize $ \\sum a_i $, we want to make as few new marks as possible — i.e., we want to avoid creating a new mark unless forced to.\n\nWhen is a new mark **forced**? \nIf $ m_i = a_{i-1} $, then **all** existing marks are above the water level. \nBut the water level on day $ i $ is at some mark — and if that mark is one of the existing ones, then the number of marks **above** it cannot be $ a_{i-1} $, because that would require the water level to be **below** all existing marks, meaning the mark at water level is not among the existing ones — contradiction.\n\nTherefore, if $ m_i = a_{i-1} $, then the water level must be **below** all existing marks, meaning a **new mark** must be created at this new lower level. \nThus: \n$$\n\\text{If } m_i = a_{i-1}, \\text{ then } a_i = a_{i-1} + 1.\n$$\n\nIf $ m_i < a_{i-1} $, then we can choose to set the water level at an existing mark such that exactly $ m_i $ marks are above it. \nIn this case, we can avoid creating a new mark: $ a_i = a_{i-1} $.\n\nTherefore, the minimal sequence $ \\{a_i\\} $ is defined recursively by: \n$$\na_0 = 0, \\\\\na_i = \n\\begin{cases}\na_{i-1} + 1 & \\text{if } m_i = a_{i-1}, \\\\\na_{i-1} & \\text{otherwise}.\n\\end{cases}\n$$\n\nThen the minimal sum of $ d_i $ is: \n$$\n\\sum_{i=1}^n d_i = \\sum_{i=1}^n (a_i - m_i - 1) = \\left( \\sum_{i=1}^n a_i \\right) - \\left( \\sum_{i=1}^n m_i \\right) - n.\n$$\n\nThus, the answer is: \n$$\n\\boxed{ \\left( \\sum_{i=1}^n a_i \\right) - \\left( \\sum_{i=1}^n m_i \\right) - n }\n$$ \nwhere $ a_i $ is computed by the recurrence above.","is_translate":false,"language":"Formal"}],"meta":{"iden":"CF924C","tags":["data structures","dp","greedy"],"sample_group":[["6\n0 1 0 3 0 2","6"],["5\n0 1 2 1 2","1"],["5\n0 1 1 2 2","0"]],"created_at":"2026-03-03 11:00:39"}}