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