UOJ Logo LFYZ Online Judge

LFYZOJ

#53. 【2018年2月期末欢乐赛】穰子与数列

统计

问题描述

穰子给了你一个长度为 $n$ 的数列,你每次可以选择相邻的两个数,并将它们中的一个替换为它们的最大公约数,请你输出把这个数列全变成 $1$ 的最少操作个数。如果永远都不可以,请输出 $-1$。

输入格式

第一行一个整数 $n$。

第二行 $n$ 个整数,第 $i$ 个代表数列中的第 $i$ 个数。

输出格式

样例一

input

5
2 2 3 4 6

output

5

样例二

input

4
2 4 6 8

output

-1

样例三

input

3
2 6 9

output

4

数据范围与约定

对于 $100\%$ 的数据,$1 \leq n \leq 2000$,$1 \leq a_i \leq 10^9$。

时间限制: $1\mathrm{s}$

内存限制: $256\mathrm{MB}$

来源

cf 891a