#include <bits/stdc++.h>
#define F first
#define S second
#define SZ(x) ((int)(x).size())
#define ALL(x) x.begin(), x.end()
#define MP make_pair
using namespace std;
using ll = long long;
using vi = vector<int>;
using vl = vector<ll>;
using vvi = vector<vi>;
using vvl = vector<vl>;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
using vii = vector<pii>;
using vll = vector<pll>;
int calc_gcd(const vi& a) {
int n = SZ(a);
int g = 0;
for (int i = 0; i < n; i++) {
g = gcd(g, a[i]);
}
return g;
}
mt19937 rng(114514);
void sol() {
int n;
cin >> n;
vi a(n);
auto start = clock();
for (int i = 0; i < n; i++) {
cin >> a[i];
}
int ans = INT_MAX;
while (clock() - start < CLOCKS_PER_SEC * 0.85) {
int x = uniform_int_distribution(0, n - 2)(rng);
int y = uniform_int_distribution(x + 1, n - 1)(rng);
int l = 0, r = 50;
while (l < r) {
int mid = l + (r-l) / 2;
bool ok = 0;
for (int da = 0; da <= mid; da++) {
int db = mid - da;
a[x] += da; a[y] += db;
if (calc_gcd(a) == 1) {
a[x] -= da; a[y] -= db;
ok = 1; break;
}
a[x] -= da; a[y] -= db;
}
if (ok) r = mid;
else l = mid + 1;
}
ans = min(ans, l);
}
cout << ans << '\n';
}
signed main() {
cin.tie(0)->sync_with_stdio(0);
sol();
}
