明确一下输出格式，第一个数是输出合法的循环移位长度 $k$ 的数量，第二个数是输出所有 $k$ 的和。看错题卡了我很久。

考虑没有修改怎么做。

注意到 $2\sim n$ 编号的餐厅没有区别，那么对于一个数列 $a$，合法的充分必要条件是：定义其前缀和数组为 $pre_i$，则 $\forall i\in[1,n),pre_i\geq i$。

所以对于没有修改的情况，可以上线段树维护前缀和相关信息。

考虑原题，这里需要用到一些 trick 和性质。

首先考虑转化 $pre_i\geq i$ 的条件，我们把每个 $a_i$ 都减少一，这样除了最后一个元素，其他在前缀和数组中的元素均需要非负。

考虑到循环移位后的前缀和是有性质的，具体地，循环移位 $x$ 次，获得的前缀和数组为 $\{b_{x+1}-b_x,b_{x+2}-b_x,\dots,b_n-b_x,b_1-b_x-1,b_2-b_x-1,\dots,-1\}$。

那么这个前缀和数组满足的性质，等价于 $\forall i\neq x,b_i-b_x-[i<x]\geq0$。容易发现这个 $x$ 只可能能是 $pre$ 靠前的最小值位置。

那么，第一问的答案只可能是 $0/1$，当且仅当 $\sum a\neq -1$ 时，第一问的答案才能为 $0$。而交换操作对前缀和的贡献相当于区间加。

所以，线段树维护区间加、查询最前面的最小值位置，就做完了。

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define fr first
#define sc second
#define pii pair<int,int>
#define yes cout<<'Y'<<'E'<<'S'<<endl
#define no cout<<'N'<<'O'<<endl
#define im cout<<-1<<endl
#define debug(x) cerr<<#x<<':'<<x<<endl
#define fo(i,l,r) for(int i=l;i<=r;i++)
#define ro(i,r,l) for(int i=r;i>=l;i--)
void Ios(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
}
const int N=5e5+5;
int n,a[N],pre[N],q;
namespace sgm{
    #define lc (x<<1)
    #define rc (x<<1|1)
    #define mid ((l+r)>>1)
    int mn[N<<2],id[N<<2],tag[N<<2];
    void pushup(int x){
        mn[x]=min(mn[lc],mn[rc]);
        if (mn[lc]<=mn[rc])
            id[x]=id[lc];
        else id[x]=id[rc];
    }
    void pushdown(int x){
        tag[lc]+=tag[x],mn[lc]+=tag[x];
        tag[rc]+=tag[x],mn[rc]+=tag[x];
        tag[x]=0;
    }
    void build(int x,int l,int r){
        if (l==r){
            id[x]=l,mn[x]=pre[l];
            return;
        }
        build(lc,l,mid);
        build(rc,mid+1,r);
        pushup(x);
    }
    void modify(int x,int l,int r,int ql,int qr,int k){
        if (ql<=l&&r<=qr){
            tag[x]+=k,mn[x]+=k;
            return;
        }
        pushdown(x);
        if (ql<=mid)
            modify(lc,l,mid,ql,qr,k);
        if (qr>mid)
            modify(rc,mid+1,r,ql,qr,k);
        pushup(x);
    }
}
using namespace sgm;
void solve(){
    cin>>n>>q;
    fo(i,1,n){
        cin>>a[i],a[i]--;
        pre[i]=pre[i-1]+a[i];
    }
    if (pre[n]!=-1){
        q++;
        while (q--)
            cout<<"0 0\n";
        return;
    }
    build(1,1,n);
    cout<<"1 "<<id[1]%n<<'\n';
    while (q--){
        int x,y;
        cin>>x>>y,x++,y++;
        if (x>y)
            swap(x,y);
        modify(1,1,n,x,y-1,a[y]-a[x]);
        swap(a[x],a[y]);
        cout<<"1 "<<id[1]%n<<'\n';
    }
}
signed main(){
    Ios();
    int T=1;
    //cin>>T;
    while (T--)
        solve();
    return 0;
}