4358: T1 团结（unite）
内存限制：512 MB
时间限制：2.000 S
评测方式：文本比较
命题人：
提交：5
解决：1
题目描述
## T1 团结（unite）
### 题目描述
小 C 有一个长度为 $n$ 的序列 $A$。
小 C 认为一个序列 $A$ 是团结的当且仅当 $\gcd(A_1,A_2,...,A_n)=1$。
小 C 现在可以做以下操作任意次：
- 选择一个位置 $i$，将 $A_i$ 变为 $\gcd(A_i,i)$，花费的代价为 $n-i+1$。
小 C 想求出使序列 $A$ 团结的最小代价和。
输入
### 输入格式
输入的第一行包含一个整数 $n$。
接下来一行包含 $n$ 个整数，第 $i$ 个整数表示 $A_i$。
输出
### 输出格式
输出共一行，包含一个整数，表示最小代价和。
样例输入 复制
2
2 4样例输出 复制
2提示
### 样例 1 输入
```
2
2 4
```
### 样例 1 输出
```
2
```
### 样例 1 解释
花费代价 $2$ 选择位置 $1$，$A_1$ 变为 $1$。
### 样例 2 输入
```
3
3 6 9
```
### 样例 2 输出
```
2
```
### 其余样例见下发文件。
### 数据规模与约定
- 对于 $30\%$ 的数据，保证 $n\le 20$。
- 对于 $60\%$ 的数据，保证 $n\le 50$。
- 对于 $100\%$ 的数据，$1\le n\le 10^5$，$1\le A_i\le 10^9$。