Day 1. Ledys Piano

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace std;
using namespace __gnu_pbds;

#define pb push_back
#define int long long
#define uint __int128
#define mp make_pair
#define left left_compile
#define right right_compile

#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")

const int INF = (int)1e18;
const int md = 998244353;
const int MAXN = (int)1e5 + 10;
const int N = (int)2e5 + 111;
const int debug = 0;
const long double eps = 1e-7;

typedef tree<
int,
null_type,
less_equal<int>,
rb_tree_tag,
tree_order_statistics_node_update>
ordered_set;

int bpow(int a,int b){
    if(b == 0)
        return 1ll;
    if(b % 2 == 0){
        int t = bpow(a,b/2);
        return (t * t) % md;
    }
    return (a * bpow(a,b-1)) % md;
}

int inv(int a){ /// return 1/a by PRIME modulo md
    return bpow(a,md-2);
}

void myerase(ordered_set& st, int t){
    int r = st.order_of_key(t);
    ordered_set::iterator it = st.find_by_order(r);
    st.erase(it);
    return;
}

mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());

void init(){

    return;
}

int t[(int)4e5+11];
int a[(int)2e5+11];

void build(int v,int l,int r){
    if(l > r)
        return;
    if(l == r){
        t[v] = a[l];
        return;
    }
    int m = (l + r) >> 1;
    build(v<<1,l,m);
    build(v<<1|1,m+1,r);
    t[v] = __gcd(t[v<<1],t[v<<1|1]);
    return;
}

int get(int v,int l,int r,int tl,int tr){
    if(l == tl && tr == r)
        return t[v];
    if(l > r || tl > tr)
        return 0;
    int m = (l + r) >> 1;
    return __gcd(get(v<<1,l,m,tl,min(tr,m)),get(v<<1|1,m+1,r,max(tl,m+1),tr));
}

void solve_case(){
    int c;
    cin >> c;
    int n;
    cin >> n;

    for(int i = 0; i < n; i++){
        cin >> a[i];
    }

    int g = a[0];
    for(int i = 0; i < n; i++){
        g = __gcd(g,a[i]);
    }

    if(c == 1){
        cout << g * n;
        return;
    }

    int cnt = 0;

    for(int i = 0; i < n; i++){
        a[i] /= g;
        cnt += (a[i] == 1);
    }

    vector<int> ans;

    if(cnt > 0){
        bool upd = true;
        while(upd){
            upd = false;
            for(int i = 0; i + 1 < n; i++){
                if(__gcd(a[i],a[i+1]) == 1 && (a[i] != 1 && a[i+1] != 1)){
                    a[i] = a[i+1] = __gcd(a[i],a[i+1]);
                    ans.pb(i+1);
                    upd = true;
                }
            }
        }

        upd = true;
        while(upd){
            upd = false;
            for(int i = 0; i + 1 < n; i++){
                if(__gcd(a[i],a[i+1]) == 1 && (a[i] != 1 || a[i+1] != 1)){
                    a[i] = a[i+1] = __gcd(a[i],a[i+1]);
                    ans.pb(i+1);
                    upd = true;
                }
            }
        }
        cout << ans.size() << "\n";
        for(auto x : ans)
            cout << x << " ";
        return;
    }

    build(1,0,n-1);

    int tl,tr;
    tl = 0, tr = n - 1;

    for(int i = 0; i < n; i++){
        if(get(1,0,n-1,i,n-1) != 1)
            break;
        int l = i + 1, r = n - 1;
        while(l - r > 1){
            int m = (l + r) >> 1;
            if(get(1,0,n-1,i,m) == 1)
                r = m;
            else
                l = m + 1;
        }
        l = (get(1,0,n-1,i,l) == 1 ? l : r);
        if(tr - tl > l - i){
            tr = l, tl = i;
        }
    }

    for(int i = tl; i < tr; i++){
        a[i] = a[i+1] = __gcd(a[i],a[i+1]);
        ans.pb(i+1);
    }

    bool upd = true;

    while(upd){
        upd = false;
        for(int i = 0; i + 1 < n; i++){
            if(__gcd(a[i],a[i+1]) == 1 && (a[i] != 1 && a[i+1] != 1)){
                a[i] = a[i+1] = __gcd(a[i],a[i+1]);
                ans.pb(i+1);
                upd = true;
            }
        }
        for(int i = 0; i + 1 < n; i++){
            if(__gcd(a[i],a[i+1]) == 1 && a[i] != a[i+1]){
                a[i] = a[i+1] = __gcd(a[i],a[i+1]);
                ans.pb(i+1);
                upd = true;
            }
        }
    }

    cout << ans.size() << "\n";
    for(auto x : ans){
        cout << x << " ";
    }

    return;
}

signed main(){
    ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
//    freopen("input.txt","r",stdin);
//    freopen("output.txt","w",stdout);

    init();

    int tests = 1;
//    cin >> tests;

    for(int _ = 1; _ <= tests; _++){
//        n = _;
        solve_case();
    }

    return 0;
}

/*

max(a[i],a[i+1],a[i+2]) - min(a[i],a[i+1],a[i+2])

-2 * a[i] - 2 * a[i+1] - 2 * a[i+2]

1
9
1 2
1 3
2 4
2 5
3 6
3 7
1 8
6 9

*/