#include<bits/stdc++.h>
#define int long long
#define ull unsigned long long
#define N 20010
using namespace std;
inline long long read()
{
	long  long x=0,f=1;char ch=getchar();
	while (ch<'0'||ch>'9'){if (ch=='-') f=-1;ch=getchar();}
	while (ch>='0'&&ch<='9'){x=x*10+ch-48;ch=getchar();}
	return x*f;
}
int a[N],b[N],l[N],r[N],d[N],p[N];
int tot,be[N],block,n,m,ysum=0;
void build()
{
    block=sqrt(n);tot=n/block;
    if(n%block!=0) tot++;
    for(int i=1;i<=n;i++) be[i]=(i-1)/block+1;
    for(int i=1;i<=tot;i++)
    {
        l[i]=(i-1)*block+1;
        r[i]=i*block;
    }
    r[tot]=n;
    for(int i=1;i<=tot;i++) sort(d+l[i],d+r[i]+1);
}
void merge(int ll,int rr)
{
    if(ll>=rr) return;
    int mid=ll+rr>>1;
    merge(ll,mid);
    merge(mid+1,rr);
    int x=ll,y=mid+1,k=ll;
    while(x<=mid && y<=rr)
    {
        if(p[x]<=p[y]) b[k++]=p[x++];
        else
        {
            b[k++]=p[y++];
            ysum+=mid-x+1;
        }
    }
    while(x<=mid) b[k++]=p[x++];
    while(y<=rr) b[k++]=p[y++];
    for(int i=ll;i<=rr;i++) p[i]=b[i];
}
signed main(){
    n=read();
    for(int i=1;i<=n;i++) a[i]=read();
    for(int i=1;i<=n;i++) p[i]=d[i]=a[i];
    build();
    merge(1,n);
    printf("%lld\n",ysum);
    m=read();
    int ans=ysum;
    while(m--)
    {
        int x,y;
        x=read();y=read();
        //cout<<a[x]<<" "<<a[y]<<" ";
        if(x>y) swap(x,y);
        if(x==y)
        {
            printf("%lld\n",ans);
            continue;
        }
        if(a[x]<a[y]) ans++;
        if(a[y]<a[x]) ans--;
        //cout<<ans<<endl;
        if(be[x]==be[y])
        {
            for(int i=x+1;i<y;i++)
            {
                if(a[i]<a[y]) ans++;
                if(a[i]>a[y]) ans--;
                if(a[i]>a[x]) ans++;
                if(a[i]<a[x]) ans--;
            }
            //cout<<ans<<endl;
        }
        else
        {
            for(int i=x+1;i<=r[be[x]];i++)
            {
                if(a[i]<a[y]) ans++;
                if(a[i]>a[y]) ans--;
                if(a[i]>a[x]) ans++;
                if(a[i]<a[x]) ans--;
            }
            //cout<<ans<<endl;
            for(int i=l[be[y]];i<y;i++)
            {
                if(a[i]<a[y]) ans++;
                if(a[i]>a[y]) ans--;
                if(a[i]>a[x]) ans++;
                if(a[i]<a[x]) ans--;
            }
            //cout<<ans<<endl;
            for(int i=be[x]+1;i<be[y];i++)
            {
                if(d[r[i]]>a[y])
                {
                    int len=upper_bound(d+l[i],d+r[i]+1,a[y])-d;
                    ans-=(r[i]-len+1);
                }
                //cout<<ans<<endl;
                //cout<<d[l[i]]<<endl;
                if(d[l[i]]<a[y])
                {
                    int len=lower_bound(d+l[i],d+r[i]+1,a[y])-d;
                    ans+=(len-l[i]);
                    if(a[len]<a[y]) ans++;
                   // cout<<"ZXZX";
                }
                //cout<<ans<<endl;
                if(d[r[i]]>a[x])
                {
                    int len=upper_bound(d+l[i],d+r[i]+1,a[x])-d;
                    ans+=(r[i]-len+1);
                }
                if(d[l[i]]<a[x])
                {
                    int len=lower_bound(d+l[i],d+r[i]+1,a[x])-d;
                    ans-=(len-l[i]);
                    if(a[len]<a[x]) ans++;
                }
            }
            //cout<<a[1]<<" "<<a[2]<<" "<<a[3]<<endl;
        }
        swap(a[x],a[y]);
        d[x]=a[x];d[y]=a[y];
        sort(d+l[be[x]],d+r[be[x]]+1);
        sort(d+l[be[y]],d+r[be[y]]+1);
        printf("%d\n",ans);
    }
	return 0;
}