#include <bits/stdc++.h>
#define yes cout<<"YES\n"
#define no cout<<"NO\n"
#define int long long
#define ff first
#define ss second
#define pb push_back
#define dd double
#define y1 zildjian
using namespace std;
const int N = 1e6+10;
const int INF = 1e18;
const int mod = 1e9+7;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
// int binpow (int a, int n) {
// if (n == 0)
// return 1;
// if (n % 2 == 1)
// return (binpow (a, n-1)%mod * a%mod)%mod;
// else {
// int b = binpow (a, n/2) % mod;
// return (b%mod * b%mod)%mod;
// }
// }
int gcd(int a, int b) {
return!b ? a : gcd(b, a % b);
}
int n;
int a[N];
int dp[N];
map<int,int> m;
void solve(){
cin>>n;
for(int i = 1;i<=n;i++) cin>>a[i];
int gc = 0;
vector<int> pos;
for(int i = 1;i<=n;i++){
int new_gc = gcd(gc,a[i]);
if(new_gc != gc) pos.pb(i);
gc = new_gc;
}
int mx = 0;
for(auto x:pos){
cout<<x<<" ";
gc = 0;
int ans = 0;
for(int i = 1;i<=n;i++){
if(i == x) continue;
gc = gcd(gc,a[i]);
ans+=gc;
}
mx = max(mx,ans);
}
cout<<endl;
cout<<mx<<'\n';
}
//bbab
signed main(){
// freopen("search.in","r",stdin);
// freopen("search.out","w",stdout);
ios_base::sync_with_stdio(0);
cin.tie(nullptr);
// cout.tie(nullptr);
int t = 1;
// cin>>t;
for(int i = 1;i<=t;i++){
// cout<<"Case "<<i<<": ";
solve();
}
}
I2luY2x1ZGUgPGJpdHMvc3RkYysrLmg+CiNkZWZpbmUgeWVzIGNvdXQ8PCJZRVNcbiIKI2RlZmluZSBubyBjb3V0PDwiTk9cbiIKI2RlZmluZSBpbnQgbG9uZyBsb25nCiNkZWZpbmUgZmYgZmlyc3QKI2RlZmluZSBzcyBzZWNvbmQKI2RlZmluZSBwYiBwdXNoX2JhY2sKI2RlZmluZSBkZCBkb3VibGUKI2RlZmluZSB5MSB6aWxkamlhbgogCnVzaW5nIG5hbWVzcGFjZSBzdGQ7CiAKY29uc3QgaW50IE4gPSAxZTYrMTA7CmNvbnN0IGludCBJTkYgPSAxZTE4Owpjb25zdCBpbnQgbW9kID0gMWU5Kzc7Cm10MTk5Mzcgcm5nKGNocm9ubzo6c3RlYWR5X2Nsb2NrOjpub3coKS50aW1lX3NpbmNlX2Vwb2NoKCkuY291bnQoKSk7CiAKIAovLyBpbnQgYmlucG93IChpbnQgYSwgaW50IG4pIHsKLy8gCWlmIChuID09IDApCi8vIAkJcmV0dXJuIDE7Ci8vIAlpZiAobiAlIDIgPT0gMSkKLy8gCQlyZXR1cm4gKGJpbnBvdyAoYSwgbi0xKSVtb2QgKiBhJW1vZCklbW9kOwovLyAJZWxzZSB7Ci8vIAkJaW50IGIgPSBiaW5wb3cgKGEsIG4vMikgJSBtb2Q7Ci8vIAkJcmV0dXJuIChiJW1vZCAqIGIlbW9kKSVtb2Q7Ci8vIAl9Ci8vIH0KaW50IGdjZChpbnQgYSwgaW50IGIpIHsKCXJldHVybiFiID8gYSA6IGdjZChiLCBhICUgYik7Cn0KaW50IG47CmludCBhW05dOwppbnQgZHBbTl07Cm1hcDxpbnQsaW50PiBtOwoKdm9pZCBzb2x2ZSgpewogICAgY2luPj5uOwogICAgZm9yKGludCBpID0gMTtpPD1uO2krKykgY2luPj5hW2ldOwogICAgaW50IGdjID0gMDsKICAgIHZlY3RvcjxpbnQ+IHBvczsKICAgIGZvcihpbnQgaSA9IDE7aTw9bjtpKyspewogICAgICAgIGludCBuZXdfZ2MgPSBnY2QoZ2MsYVtpXSk7CiAgICAgICAgaWYobmV3X2djICE9IGdjKSBwb3MucGIoaSk7CiAgICAgICAgZ2MgPSBuZXdfZ2M7CiAgICB9CiAgICBpbnQgbXggPSAwOwogICAgZm9yKGF1dG8geDpwb3MpewogICAgCWNvdXQ8PHg8PCIgIjsKICAgICAgICBnYyA9IDA7CiAgICAgICAgaW50IGFucyA9IDA7CiAgICAgICAgZm9yKGludCBpID0gMTtpPD1uO2krKyl7CiAgICAgICAgICAgIGlmKGkgPT0geCkgY29udGludWU7CiAgICAgICAgICAgIGdjID0gZ2NkKGdjLGFbaV0pOwogICAgICAgICAgICBhbnMrPWdjOwogICAgICAgIH0KICAgICAgICBteCA9IG1heChteCxhbnMpOwogICAgfQogICAgY291dDw8ZW5kbDsKICAgIGNvdXQ8PG14PDwnXG4nOwp9CgovL2JiYWIKCnNpZ25lZCBtYWluKCl7CiAgICAvLyBmcmVvcGVuKCJzZWFyY2guaW4iLCJyIixzdGRpbik7IAogICAgLy8gZnJlb3Blbigic2VhcmNoLm91dCIsInciLHN0ZG91dCk7CiAgICBpb3NfYmFzZTo6c3luY193aXRoX3N0ZGlvKDApOwogICAgY2luLnRpZShudWxscHRyKTsKICAgIC8vIGNvdXQudGllKG51bGxwdHIpOwogICAgaW50IHQgPSAxOwogICAgLy8gY2luPj50OwogICAgZm9yKGludCBpID0gMTtpPD10O2krKyl7CiAgICAgICAgLy8gY291dDw8IkNhc2UgIjw8aTw8IjogIjsKICAgICAgICBzb2x2ZSgpOwogICAgfQp9