该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

说明

时间限制：1 Sec 内存限制：256 MB 输入文件：score.in 输出文件：score.out

小明的爱好是竞技编程，每天都沉浸在各类竞赛中。在竞技编程竞赛里，选手通常都会有对应的 Rating 值。

现有一个包含 $N$ 个元素的数组 $A$，按时间顺序记录了小明参加 $N$ 次竞赛后的 Rating 值。其中，第 $i$ 次竞赛结束后，他的 Rating 值为 $A_i$。

由于自己的 Rating 值一直停滞不前，小明感到十分懊恼，于是决定对这份 Rating 记录进行修改篡改，让它变成严格单调递增的序列。每次操作可以从 $N$ 条 Rating 记录中任选一条，将其修改为任意一个正整数。他计划通过若干次这样的操作，让 Rating 值按时间顺序呈现出严格单调递增的趋势。

请你计算出完成这项修改所需的最少操作次数。

其中，Rating 值按时间顺序呈严格单调递增，定义为满足 $A_1 \lt A_2 \lt \dots \lt A_{N-1} \lt A_N$ 这一条件。

输入格式

第一行一个整数 $N$。

第二行 $N$ 个整数 $A_1,A_2,\ldots,A_N$。

输出格式

一个整数，表示答案。

样例

样例 1

6
1 1 4 5 1 4

3

样例说明：

例如，通过对 $A_2$、$A_5$、$A_6$ 这 $3$ 个元素进行操作，可将数组 $A$ 修改为 $\{1, 2, 4, 5, 6, 7\}$，使其成为严格单调递增数组。

需要注意的是，若不修改 $A_2$，得到的数组 $\{1, 1, 4, 5, 6, 7\}$ 并不满足严格单调递增的条件。

样例 2

9
333 111 444 111 555 999999999 222 666 555

5

样例说明：

例如，通过 $5$ 次操作将数组修改为 $\{100, 111, 444, 500, 555, 999999999, 1000000000, 1000000001, 1000000002\}$，这是所需的最少操作次数。

请注意，输入数组 $A$ 的元素最大值为 $10^9$，但对操作后元素的取值没有此类限制，操作后的值可大于 $10^9$。

样例 3

20
99922 3916262 22 35176942 700 7841 2792958 812325 516 15108 68477 4892660 894 84778 1537710 31499 5844 93505127 493351 815

12

数据范围

对于 8% 的数据，$N \le 100$，$A_i \le 100$。

对于 16% 的数据，$N \le 100$，$A_i \le 2 \times 10^5$。

对于 40% 的数据，$N \le 100$。

另有 4% 的数据，$N \le 2 \times 10^5$，$A_i \le 10$。

对于 100% 的数据，$1 \le N \le 2 \times 10^5$，$1 \le A_i \le 10^9$。