$1 \le n \le 3.5 \times 10 ^ 4, 1 \le a_i \le 10 ^ 5$

题面很简约，长度为 $n$ 的整数序列 $a$，我们要保证这个东西在修改完之后是严格单调递增的，第一问问我们最少改变的数的个数。

很朴素的思路是我们先求出 LIS，再直接用 $n - l$ 就是答案，但是这样是错的，我们看这个样例：

4
1 2 2 3

对于这个来说，我们的 LIS 选出的长度显然是 $3$，就是 $\{ 1, 2, 3\}$，这样的话我们的代码误以为我们只需要对 $2$ 修改即可，但是实际上并非这样，我们的 $2$ 无法修改为 $2 \sim 3$ 中间的任何 $Z$。

那怎么办呢？我们选择 $a_i$ 和 $a_j$ 作为一对上升的序列中的一部分的条件不止 $a_i < a_j$，我们发现其还满足 $a_j - a_i \ge j - i$，我们对其移项得到 $a_j - j \ge a_i - i$，那么我们直接重标号，定义数组 $b$，使得 $b_i = a_i - i$，那么我们只需要对于这个 $b$ 求 LIS 即可，答案就是 $n - l$。

对于第二问，其要求我们在第一问的基础上，对选出的这最少的进行修改，使得修改的绝对值之和最小。

我们要把 $a$ 变成严格上升的和 $b$ 变成单调不降的修改的答案应当是一样的，我们这里做一个简单证明，对于 $a_i$ 和 $a_{i + 1}$ 来说，我们要求的是 $a_i < a_{i + 1} \rightarrow a_i + 1 \le a_{i + 1}$，而我们的 $b_{i} = a_i - i$，那么我们的 $b_i - i \le b_{i + 1} - i - 1 \rightarrow a_i + 1 \le a_{i + 1}$。好的我们已经证明了问题是等价的，那么我们去解决 $b$ 的单调不降问题即可。

接下来我们考虑这样的问题，定义集合 $T \in S$，$T$ 是其全集 $S$ 的 $\preceq$，我们现在要解决的是 $A \notin T$ 的这些应该把题面放到哪里呢？

我们考虑假设我们已经考虑好前 $i$ 个元素的答案是 $f_i$，我们现在要求你从这个 $i$ 转移到下一个 LIS 加 $1$ 的位置怎么转移。我们现在问题在于中间的 $[i + 1, j - 1]$ 的区间的点全是要么 $< b_i$ 的，要么是落在 $> b_j$ 的，如下图：

我们应当如何调整中间的 $b$ 呢？我们要求 $b$ 单调不降，那么我们至少是 $b_i \le b_{i + 1}$，我们至少需要让这些东西全落在黄色的部分。

那么如何做到最小呢，我们显然是尽可能的使其贴近边框，我们称以一个点 $k \in [i + 1, j - 1]$ 的部分，我们使得 $[i + 1, k]$ 的部分直接移动到下边框上，$[k + 1, j - 1]$ 的部分我们直接移动到上边框上，这个时候一定是有最优解的。如下图：

如何证明这个解是最优解呢，我们考虑这样的折中方案（毕竟人脑觉得很优），如下图：

我们定义这样的紫色平台中的从上方降下来的为 $Y$，从下方升上来的为 $X$，那么分为以下三中情况：

1. $X > Y$

   那么我们说，如果将所有紫色平台全部降下去，由于 $X > Y$ 的缘故，最终的 $\Delta > 0$，我们刚刚的方案是优的。

2. $X < Y$

   那么这种情况是和上面的是对称的，我们将所有平台升上去，最终的 $\Delta > 0$，所以也优。

3. $X = Y$

   这种情况在中间和两边共享最优方案。

因此，我们证明了刚刚的划分方式一定包含最优解。

那么最终的实现还是不是很好实现的，我们将上述的内容转成式子，可以得到下式：

$$dp_j = \min \{ dp_j, dp_i + \sum_{p = i + 1} ^ k |b_p - b_i| + \sum_{p = k + 1} ^ {j - 1} |b_p - b_j| \}$$

我们注意到这个式子的两个 $\sum$ 可以在每一轮直接用前后缀和预处理出来，可是你的 $i, j$ 的枚举就已经达到了 $\mathcal{O}(n ^ 2)$，怎么办呢？

我们发现很多地方的枚举是无效的，我们需要使得 $j$ 的位置的结尾的 LIS 长度恰好为 $i$ 位置为结尾的 LIS 的长度 $+1$，那么我们直接开一个 vector 来记录长度为 $i$ 的下标的下标集合，这样我们枚举 $j$，只需要从 $l_j - 1$ 的长度的下标的地方转移，这是一个很大的优化。因为随机数据下 LIS 长度的期望是 $\mathcal{O}(\sqrt{n})$，那么实际上我们最终的复杂度期望在 $\mathcal{O}(n \sqrt{n})$ 左右，对于 $3.5 \times 10 ^ 4$ 的数据也是轻松通过。