D. Riverside Curio

[{"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]。在第二个例子中，下图展示了一种最优情况。 "}]}

Let $ n $ be the number of days. Let $ 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 $. Let $ d_i $ denote the number of marks strictly **below** the water level on day $ i $. Let $ a_i $ denote the total number of distinct marks on the channel at the end of day $ i $. Let $ h_i $ denote the water level on day $ i $ (a real number, representing the height of the mark made on day $ i $, if any). **Constraints:** - On day $ i $, the number of marks strictly above the water level is $ m_i $. - Since marks are never removed, the total number of distinct marks at the end of day $ i $ satisfies: $$ a_i = a_{i-1} + \delta_i, \quad \text{where } \delta_i = \begin{cases} 1 & \text{if a new mark is made on day } i \\ 0 & \text{otherwise} \end{cases} $$ - The water level on day $ i $ is exactly the height of the mark made on that day (if a new mark is made), or coincides with an existing mark (if not). - The number of marks **strictly above** the water level on day $ i $ is $ m_i $, so: $$ m_i = a_i - 1 - d_i \quad \text{(since total marks } a_i \text{, one at water level, } d_i \text{ below)} $$ Rearranged: $$ d_i = a_i - 1 - m_i $$ We are to **minimize** $ \sum_{i=1}^n d_i = \sum_{i=1}^n (a_i - 1 - m_i) = \left( \sum_{i=1}^n a_i \right) - n - \sum_{i=1}^n m_i $ Since $ \sum m_i $ is fixed, minimizing $ \sum d_i $ is equivalent to minimizing $ \sum_{i=1}^n a_i $. Now, $ a_i $ is non-decreasing, $ a_0 = 0 $, and $ a_i \geq m_i + 1 $ (because at least $ m_i $ marks above + 1 at water level). Moreover, to satisfy the condition on day $ i $, we must have at least $ m_i + 1 $ marks total by day $ i $, so: $$ a_i \geq \max(a_{i-1}, m_i + 1) $$ To minimize $ \sum a_i $, we choose the minimal possible $ a_i $ at each step: $$ a_i = \max(a_{i-1}, m_i + 1) $$ with $ a_0 = 0 $. Then, the minimal possible sum of $ d_i $ is: $$ \sum_{i=1}^n d_i = \sum_{i=1}^n (a_i - 1 - m_i) = \left( \sum_{i=1}^n a_i \right) - n - \sum_{i=1}^n m_i $$ where $ a_i = \max(a_{i-1}, m_i + 1) $, $ a_0 = 0 $. --- **Final Formal Statement:** Given $ n \in \mathbb{Z}^+ $ and a sequence $ m_1, m_2, \dots, m_n \in \mathbb{Z} $ with $ 0 \leq m_i < i $, define $ a_0 = 0 $ and for $ i = 1 $ to $ n $: $$ a_i = \max(a_{i-1}, m_i + 1) $$ Then the minimal possible sum of $ d_i $ is: $$ \boxed{\sum_{i=1}^{n} (a_i - 1 - m_i)} $$