#include <bits/stdc++.h>

using namespace std;

#define int long long
#define mp make_pair
#define pb push_back

const int N = (int)1e5 + 1;
const int UNDEFINED = -(int)1e12;
vector<int> a;

int t[4*N];

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

void update(int v,int l,int r,int pos,int new_val)
{
    if(l == r)
    {
        t[v] = new_val;
        a[l] = new_val;
        return;
    }
    int m = (l + r) / 2;
    if(pos <= m)
        update((v<<1),l,m,pos,new_val);
    else
        update((v<<1)|1,m+1,r,pos,new_val);
    t[v] = __gcd(t[(v<<1)],t[(v<<1)|1]);
    return;
}

int get(int v,int l,int r,int tl,int tr)
{
    if(v == 0)
        exit(0);
//    cerr << v << " " << l << " " << r << " " << tl << " " << tr << "\n";
    if(l == tl && r == tr)
        return t[v];
    if(l > r || tl > tr)
        return UNDEFINED;
    int m = (l + r) / 2;
    int c1 = UNDEFINED;
    int c2 = UNDEFINED;
    if(tl >= l)
        c1 = get((v<<1),l,m,tl,min(tr,m));
    if(tr <= r)
        c2 = get((v<<1)|1,m+1,r,max(m+1,tl),tr);
    return (c1 == UNDEFINED ? c2 : (c2 == UNDEFINED ? c1 : __gcd(c1,c2)));
}

int n,q;

int pref_sum(int pos,vector<pair<int,int> >& pref)
{
    int cur = 1;
    int ans = 0;
    for(int i = 0; i < pref.size(); i++)
    {
        if(cur + pref[i].second > pos)
        {
            ans += max(0ll,(pos - cur + 1)) * pref[i].first;
            break;
        }
        cur += pref[i].second;
        ans += pref[i].first * pref[i].second;
    }
    return ans;
}

int suf_sum(int pos,vector<pair<int,int> >& suf)
{
    int cur = 1;
    int ans = 0;
    for(int i = 0; i < suf.size(); i++)
    {
        if(cur + suf[i].second > pos)
        {
            ans += max(0ll,(pos - cur + 1)) * suf[i].first;
            break;
        }
        cur += suf[i].second;
        ans += suf[i].first * suf[i].second;
    }
    return ans;
}

int F(int j,vector<pair<int,int> >& pref, vector<pair<int,int> >& suf)
{
//    cout << "F: ";
//    cout << j << " " << n - j - 1 << " | ";
//    cout << pref_sum(j,pref) << " " << suf_sum(n - j - 1,suf) << "\n";
    return pref_sum(j,pref) + suf_sum(n - j - 1,suf);
}

int go(int v,int l,int r,int tl,int tr,int val,int cur)
{
    if(tl > tr)
        return 1;
    if(l == r)
    {
        cur = __gcd(cur,a[l]);
        if(val == cur)
            return r;
        return -1;
    }
    int m = (l + r) / 2;
    if(tl == l && tr == r)
    {
        if(__gcd(cur,a[l]) != val)
            return -1;
        int rght = __gcd(cur,t[v<<1]);
        if(val != rght)
            return go(v<<1,l,m,tl,min(m,tr),val,cur);
        rght = __gcd(rght,a[m+1]);
        if(val != rght)
            return m;
        return go(v<<1|1,m+1,r,max(tl,m+1),r,val,__gcd(cur,t[v<<1]));
    }
    int R = go(v<<1|1,m + 1,r,max(m+1,tl),tr,val,__gcd(cur,t[v<<1]));
    if(R != -1)
        return R;
    return go(v<<1,l,m,tl,min(m,r),val,cur);
}

int solve()
{
    int y;
    int i = 0;
    vector<pair<int,int> > pref;
    vector<pair<int,int> > suf;
    int l,r;
    int m = 0;
    int tmp;
    while(i < n - 1)
    {
        tmp = get(1,0,n-1,0,i);
        r = go(1,0,n-1,0,i,tmp,0);
    }

    i = n - 1;

    while(i > 0)
    {
        y = get(1,0,n-1,i,n-1);

    }

    reverse(suf.begin(),suf.end());
    reverse(pref.begin(),pref.end());

//    cout << "Pref:\n";
//    for(auto x : pref)
//        cout << x.first << " " << x.second << "\n";
//
//    cout << "Suf:\n";
//    for(auto x : suf)
//        cout << x.first << " " << x.second << "\n";
//
//    cout << "\n";

    int mn = -UNDEFINED;
    l = 0, r = n - 1;

    int c1,c2;

    while(r - l > 1)
    {
        m = (l + r) / 2;
        if(F(m,pref,suf) > F(m+1,pref,suf))
            l = m + 1;
        else
            r = m;
//        cout << l << " " << r << "\n";
    }

    mn = F(l,pref,suf);

    if(r - l >= 1)
    {
        for(int T = l + 1; T <= r; T++)
            mn = min(mn,F(T,pref,suf));
    }

//    cout << mn << "\n";

    return mn + t[1];
}

signed main()
{
    ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);

//    freopen("input.txt","r",stdin);
//    freopen("output.txt","w",stdout);

    cin >> n >> q;

    a.resize(n);

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

    build(1,0,n-1);

//    cerr << "BUILD\n";

    /// QUERIES

    cout << solve() << "\n";

    int pos,x;

    while(q--)
    {
        cin >> pos >> x;
        update(1,0,n-1,pos-1,x);
        cout << solve() << "\n";
    }

    return 0;
}