Cân bằng dãy
Cho dãy $a_1,a_2,...,a_N$. Cân bằng dãy là việc làm cho các phần tử của dãy bằng nhau.
Bạn có thể thực hiện thao tác sau một số lần (hoặc không thực hiện): Tạo dãy $b$ có ít hơn một phần tử theo công thức: $b_i=gcd(a_i,a_{i+1})$ và thay thế dãy $a$ bởi dãy $b$ mới tạo.
Hãy cho biết số thao tác ít nhất để dãy trở nên cân bằng.
Dữ liệu
- Dòng đầu tiên chứa hai số nguyên $N \ (0<N\le 10^5)$;
- Dòng thứ hai chứa $N$ số nguyên $a_i \ (0<a_i\le 10^9)$.
Kết quả
- Kết quả bài toán.
Ví dụ
Ví dụ 1
input
4
16 24 10 5
output
3
Ví dụ 2
input
6
9 9 27 9 9 63
output
1
Comments