全wa求调

#include <bits/stdc++.h>
#define int long long
using namespace std;
inline int read() {
	register int x=0;
	register bool f=0;
	register char c=getchar();
	while(c<'0'||c>'9') {
		if(c=='-') f=1;
		c=getchar();
	}
	while(c>='0'&&c<='9') {
		x=(x<<3)+(x<<1)+c-48;
		c=getchar();
	}
	return f?-x:x;
}
const int N=2e5+10;
const int inf=2147483647;
int lsh[N<<1],rt[N],n,m,len;
int tmp[N],tem[N],tot,cnt,num,a[N],ans,v[N];
struct node{
	struct Node{
		int ls,rs,v;
	}w[N<<8];
	inline void chg(int &u,int l,int r,int k,int x){
		if(!u)u=++tot;
		w[u].v+=x;
		if(l==r)return;
		int mid=(l+r)>>1;
		if(k<=mid)chg(w[u].ls,l,mid,k,x);
		else chg(w[u].rs,mid+1,r,k,x);
	}
	inline int qry_rk(int l,int r,int k,int op){
		int sum=0;
		if(l==r){
			for(int i=1;i<=cnt;i++)sum+=w[w[tmp[i]].ls].v;
			for(int i=1;i<=num;i++)sum-=w[w[tem[i]].ls].v;
			return op*sum;
		}
		int mid=l+r>>1;
		if(k<=mid){
			for(int i=1;i<=cnt;i++)tmp[i]=w[tmp[i]].ls;
			for(int i=1;i<=num;i++)tem[i]=w[tem[i]].ls;
			return qry_rk(l,mid,k,op);
		}else{
			for(int i=1;i<=cnt;i++)sum+=w[w[tmp[i]].ls].v,tmp[i]=w[tmp[i]].rs;
			for(int i=1;i<=num;i++)sum-=w[w[tem[i]].ls].v,tem[i]=w[tem[i]].rs;
			return sum+qry_rk(mid+1,r,k,op);
		}
	}
	
}seg;
struct Tre_a{
	inline int lb(int x){
		return x&(-x);
	}
	inline void Add(int u,int x){
		for(int i=u;i<=n;i+=lb(i)){
			seg.chg(rt[i],1,len,a[u],x);
		}
	}
	inline int fid_rk(int l,int r,int k,int op){
		num=cnt=0;
		for(int i=r;i;i-=lb(i))tmp[++cnt]=rt[i];
		for(int i=l-1;i;i-=lb(i))tem[++num]=rt[i];
		return seg.qry_rk(1,len,k,op);
	}
}tre;
signed main() {
	freopen("P12685.in","r",stdin);
	freopen("P12685.ansme","w",stdout);
	n=read();
	for(int i=1; i<=n; i++) {
		lsh[i]=a[i]=read();
	}
	sort(lsh+1,lsh+1+n);
	len=unique(lsh+1,lsh+1+n)-lsh-1;
	for(int i=1; i<=n; i++) {
		a[i]=lower_bound(lsh+1,lsh+1+len,a[i])-lsh;
		tre.Add(i,1);
	}
	for(int i=1;i<=n;i++)ans+=tre.fid_rk(i,n,a[i],0);
	m=read();
	printf("%lld\n",ans);
	while(m--){
		int x=read(),y=read();
		if(x>y)swap(x,y);
		int num=y-x+1,ax=a[x],ay=a[y],vx=v[x],vy=v[y];
		if(a[y]<a[x])ans++;
		else if(a[x]<a[y]) ans--;
		int old=tre.fid_rk(x,y,a[x],0)+num-tre.fid_rk(x,y,a[y],1);
		tre.Add(x,-vx),tre.Add(x,vx);
		tre.Add(y,-vy),tre.Add(y,vy);
		swap(a[x],a[y]);swap(v[x],v[y]);
		int nw=tre.fid_rk(x,y,a[x],0)+num-tre.fid_rk(x,y,a[y],1);
		ans=ans+nw-old;
		printf("%lld\n",ans);
	}
}