Cho một dãy \(a\) gồm \(n\) số nguyên dương. Số thứ \(i\) của dãy là \(a_i\). Mỗi thao tác ta có thể chọn một số của dãy \(a\) và cộng nó lên \(1\) hoặc trừ nó cho \(1\), sao cho các số của dãy vẫn nguyên dương. Một dãy được gọi là đẹp nếu ước chung lớn nhất của cả dãy khác \(1\).

Yêu cầu: Hãy tìm số thao tác ít nhất để làm cho dãy \(a\) đẹp.

Input

• Dòng đầu tiên gồm một số nguyên dương \(n\) \((1 \leq n \leq 2 \times 10^5)\).
• Dòng thứ hai gồm \(n\) số nguyên dương \(a_1, a_2, \ldots, a_n\) \((1 \leq a_i \leq 10^{12})\).

Output

• Gồm một số nguyên duy nhất là số thao tác ít nhất để làm cho dãy \(a\) đẹp.

Example

3
6 7 6

1

2
18 18

0

Scoring

• Subtask 1 (\(18\%\) số điểm): \(a_i \leq 20\), \(\forall 1 \leq i \leq n\).
• Subtask 2 (\(23\%\) số điểm): \(a_i \leq 10^6\).
• Subtask 3 (\(59\%\) số điểm): Không có ràng buộc gì thêm.