Collecting Numbers II

1#include<bits/stdc++.h>
2using namespace std;
3#define int long long
4signed main(){
5  ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
6  int n,q; cin>>n>>q;
7  int a[n+2],p[n+2],ans=1; p[0]=0,p[n+1]=n+1;
8  for(int i=1;i<=n;++i)
9    cin>>a[i],p[a[i]]=i;
10  for(int i=1;i<=n;++i)
11    if(p[i]<p[i-1]) ++ans;
12  while(q--){
13    int r,s; cin>>r>>s;
14    int x=a[r],y=a[s];
15    if(x>y) swap(x,y);
16    ans-=(p[x-1]>p[x])+(p[x]>p[x+1])
17        +(p[y-1]>p[y])+(p[y]>p[y+1]);
18    if(y==x+1) ans+=(p[x]>p[y]);
19    swap(a[r],a[s]); swap(p[x],p[y]);
20    ans+=(p[x-1]>p[x])+(p[x]>p[x+1])
21        +(p[y-1]>p[y])+(p[y]>p[y+1]);
22    if(y==x+1) ans-=(p[x]>p[y]);
23    cout<<ans<<'\n';
24  }
25  return 0;
26}