← 返回题目列表

Codeforces · 946/G

G. 几乎增加阵列

中文机器翻译题面 查看原题

如果我们可以从数组中删除不超过一个元素,从而使数组变得严格递增(即每个元素都严格大于它之前的每个元素),则我们称该数组为几乎递增数组。

给定一个由 n 个元素组成的数组 a。您可以用任何整数替换任何元素(并且您可以根据需要多次这样做)。为了使数组几乎增加,您必须执行的最少替换次数是多少?

输入

第一行包含一个整数 n (2 ≤ n ≤ 200000) — a 中的元素数量。

第二行包含 n 个整数 a1, a2, ..., an (1 ≤ ai ≤ 109) — 数组 a。

输出

打印您必须执行的最小替换次数,以便 a 几乎增加。

示例

输入 #1

5
5 4 3 2 1

输出 #1

3

输入 #2

5
1 2 8 9 5

输出 #2

0