#include <bits/stdc++.h>
using namespace std;
template<typename A, typename B> ostream& operator<<(ostream &os, const pair<A, B> &p) { return os << '(' << p.first << ", " << p.second << ')'; }
template<typename T_container, typename T = typename enable_if<!is_same<T_container, string>::value, typename T_container::value_type>::type> ostream& operator<<(ostream &os, const T_container &v) { os << '{'; string sep; for (const T &x : v) os << sep << x, sep = ", "; return os << '}'; }
void dbg_out() { cerr << endl; }
template<typename Head, typename... Tail> void dbg_out(Head H, Tail... T) { cerr << ' ' << H; dbg_out(T...); }
#ifdef WA_DEBUG
#define dbg(...) cerr << "(" << #__VA_ARGS__ << "):", dbg_out(__VA_ARGS__)
#else
#define dbg(...)
#endif

using ll  = long long;
using ull = unsigned long long;
#define pb push_back
#define fi first
#define se second
#define rep(i,a,b) for(int i=int(a);i<=(int)(b);i++)
#define per(i,a,b) for(int i=int(a);i>=(int)(b);i--)
const int mod  = 1e9+7;
const int inf  = 0x3f3f3f3f;
const int maxn = 1e5+10;
int main() {
#ifndef WA_DEBUG
    ios::sync_with_stdio(false);cin.tie(nullptr);
#endif
    int n;
    cin>>n;
    vector<int> a(n+1);
    int Min=inf;
    rep(i,1,n) {
        cin>>a[i];
        Min=min(a[i],Min);
    }
    set<int> s;
    rep(i,1,n) {
        rep(j,1,maxn) {
            if(j*j>a[i]) break;
            if(a[i]%j==0) {
                s.insert(j);
                if(j*j!=a[i]) s.insert(a[i]/j);
            }
        }
    }
    int cnt=0;
    for(int x:s) {
        int ans=-1;
        rep(i,1,n) {
            if(a[i]%x==0) {
                if(ans==-1) ans=a[i]/x;
                else ans=__gcd(ans,a[i]/x);
            }
        }
        if(ans==1&&x<=Min) cnt++;
    }
    cout<<cnt<<'\n';
    return 0;
}


#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define fi first
#define se second
#define int long long int
#define pii pair<int,int>
const int INF= 1e12;
const int MAX=5e6+5;
const int MAXK=105;
const int mod = 1e9+7;
int gcd(int a, int b)
{
    while(b!=0)
    {
        a=a%b;
        swap(a,b);
    }
    return a;
}
int binpow(int a,int b)
{
    int res=1;
    while(b>0)
    {
        if(b%2==1)
            res=res*a%mod;
        a=a*a%mod;
        b/=2;
    }
    return res;
}
/*
 * check modulus when using binpow
 */
map<int,int> mp;
int find_set(int x)
{
    if(mp[x]==x)
    {
        return x;
    }
    return mp[x]=find_set(mp[x]);
}
void solve()
{
    int cnt=0;
    int n;
    cin>>n;
    int ar[n];
    for(int i=0;i<n;i++)
    {
        cin>>ar[i];
        mp[ar[i]]=ar[i];
    }
    for(int i=0;i<n/2;i++)
    {
        int x=find_set(ar[i]);
        int y=find_set(ar[n-1-i]);
        if(x!=y)
        {
            cnt++;
            mp[x]=y;
        }
    }
    cout<<cnt<<"\n";




}
int32_t main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
#ifndef ONLINE_JUDGE
   freopen("input.txt","r",stdin);
    freopen("output.txt","w",stdout);
#endif // ONLINE_JUDGE
    int t=1;
    //cin>>t;
    for(int i=1;i<=t;i++)
    {
        //cout<<"Case #"<<i<<": ";
        solve();
    }
}