Cân bằng dãy


Submit solution

Points: 1
Time limit: 1.0s
Memory limit: 1G

Problem type

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

There are no comments at the moment.