Description

给定一个长度为 n 的整数数组 a，你可以执行任意次修改操作：选择数组中的某个元素 a[i]，将其替换为原数组中存在过的任意整数（不能使用原数组没有的数字，无正负限制）。

请计算最少需要执行多少次修改操作，使得修改后的数组满足以下约束：对于所有 2 ≤ i ≤ n（对应数组索引 1 ≤ i < n），a[i] 仅能取两个合法值之一：

a[i] = a[i-1]（与前一个元素相等）

a[i] = a[i-1] + 1（比前一个元素大 1）

Format

Input

第一行输入一个整数 n（1 ≤ n ≤ 1000）

第二行输入 n 个整数 a[1..n]（-10^5 ≤ a[i] ≤ 10^5，数组中可能存在重复元素）

Output

输出一个整数，表示最少修改次数

Samples

6
1 2 2 4 3 5

2

5
5 7 7 9 8

2

Limitation

1s, 1024KiB for each test case.