Karrar- một chú ROBOT sắp xếp hàng hóa. Ngày tết đã đến và có rất nhiều hàng hóa được chuyển đến. Karrar có nhiệm vụ phải sắp xếp hàng hóa theo thùng sao cho ước chung lớn nhất của tất cả các kiện hàng trong thùng phải lớn hơn 1 (có thể có thùng không có kiện hàng nào, các thùng hàng được xếp cạnh nhau). Karrar làm việc bằng cách chọn một kiện hàng ở một thùng nhất định rồi di chuyển sang 1 trong 2 thùng cạnh bên, việc này khiến Karrar tốn 1 năng lượng. Hãy tính số năng lượng ít nhất để Karrar có thể hoàn thành nhiệm vụ.

Dữ liệu:

Input:

-Dòng đầu tiên chứa số nguyên dương n (n<=10^6) là số thùng hàng.

-Dòng tiếp theo chứa n số a1,a2,a3...,an số là số kiện hàng trong từng thùng. (ai<=10^6)

Output:

-Số năng lượng ít nhất để hoàn thành nhiệm vụ.