### 题目描述 GCD 王国的花园中有连续摆放着 $n$ 个花坛，每个花坛有一个美丽值 $a_i$ 。 若存在连续的若干个花坛的美丽值的最大公约数等于该花坛的个数，或者说是存在一对下标 $l$ 和 $r（1 ≤ l ≤ r ≤ n）$，使得 $l$ 到 $r$ 的美丽值的最大公约数等于 $r-l+1$，国王会感到非常难受。 你可以将任意一个花坛的美丽值改为任意正整数，当然这成本非常高。请问最少需要改变几个花坛的美丽值，才能让国王感到舒适？ ### 输入格式 第一行输入一个整数 $n$ ，表示花坛的个数。 第二行输入 $n$ 个整数 $a_1，a_2，......，a_n$，表示花坛的美丽值。 数据保证 $1\leq n \leq 2 \times 10^5$，$1 \leq a_i \leq 10^9$。 ### 输出格式 输出一个整数，表示答案。 ### 样例输入 ``` 3 1 2 3 ``` ### 样例输出 ``` 1 ``` ### 说明 对于样例，一种可行的修改方案为将 $[1,2,3]$ 变为 $[3,2,3]$，这只需要改变第一个花坛的美丽值。