#include<cstdio>

#include<iostream>

#include<cstring>

#define MAXN 100010

using namespace std;

typedef long long LL;

typedef double D;

const D a=0.756;

LL ans;

struct ScapeGoat_Tree

{

    ScapeGoat_Tree *ch[];

    int key,size,cover,ex;

    bool bad()

    {

      return cover*a+<ch[]->cover||cover*a+<ch[]->cover;

    }

    void pushup()

    {

       size=ch[]->size+ch[]->size+ex;

       cover=ch[]->cover+ch[]->cover+;

    }

}*null,*stack[(MAXN<<)+],pool[(MAXN<<)+],*lst[(MAXN<<)+];

int  top,len;

inline void Init()

{

    null=pool;

    null->ch[]=null->ch[]=null;

    null->key=null->size=null->cover=null->ex=;

    for(int  i=;i<(MAXN<<);i++)stack[++top]=pool+i;

}

inline ScapeGoat_Tree *New(int  key)

{

    ScapeGoat_Tree *p=stack[top--];

    p->ch[]=p->ch[]=null;

    p->key=key;

    p->size=p->ex=p->cover=;

    return p;

}

struct Tree

{

    Tree *ch[];

    int  mid,l,r;

    ScapeGoat_Tree *root;

    Tree(){ch[]=ch[]=NULL;mid=l=r=;root=null;}

    void* operator new(size_t size);

}*root,*C,*mempool;

void* Tree :: operator new(size_t size)

{

    if(C==mempool)

    {

       C=new Tree[(<<)+];

       mempool=C+(<<)+;

    }

    C->root=null;

    return C++;

}

void travel(ScapeGoat_Tree *p)

{

    if(p==null)return;

    travel(p->ch[]);

    if(p->ex)lst[++len]=p;

    else stack[++top]=p;

    travel(p->ch[]);

}

ScapeGoat_Tree *divide(int  l,int  r)

{

    if(l>r)return null;

    int  mid=(l+r)>>;

    lst[mid]->ch[]=divide(l,mid-);

    lst[mid]->ch[]=divide(mid+,r);

    lst[mid]->pushup();

    return lst[mid];

}

inline void rebuild(ScapeGoat_Tree *&p)

{

    len=;

    travel(p);

    p=divide(,len);

}

ScapeGoat_Tree **insert(ScapeGoat_Tree *&p,int  key)

{

    if(p==null )

    {

      p=New(key);

      return &null;

    }

    p->size++;

    p->cover++;

    ScapeGoat_Tree **ret=insert(p->ch[p->key<=key],key);

    if(p->bad())ret=&p;

    return ret;

}

inline void Insert(ScapeGoat_Tree *&Root,int  key)

{

    ScapeGoat_Tree **p=insert(Root,key);

    if(*p!=null )rebuild(*p);

}

inline int  Rank_Max(ScapeGoat_Tree *Root,int  key)

{

    ScapeGoat_Tree *now=Root;

    int  ret=;

    while(now!=null )

     if(now->key<=key)

      now=now->ch[];

     else

      ret+=now->ch[]->size+now->ex,now=now->ch[];

    return ret;

}

inline int  Rank_Min(ScapeGoat_Tree *Root,int key)

{

    ScapeGoat_Tree *now=Root;

    int  ret=;

    while(now!=null )

     if(now->key>=key)

      now=now->ch[];

     else

      ret+=now->ch[]->size+now->ex,now=now->ch[];

    return ret;

}

void del(ScapeGoat_Tree *p,int k)

{

    p->size--;

    if(p->ex&&p->ch[]->size+==k)

    {

      p->ex=;

      return;

    }

    if(p->ch[]->size>=k) del(p->ch[],k);

    else del(p->ch[],k-p->ch[]->size-p->ex);

}

inline void Del(ScapeGoat_Tree *&Root,int  key)

{

    del(Root,Rank_Min(Root,key)+);

    if(Root->size<Root->cover*a)rebuild(Root);

}

int  n,m,pos[MAXN];

void build(Tree *p)

{

     p->mid=(p->l+p->r)>>;

     if(p->l==p->r)return;

     p->ch[]=new Tree;

     p->ch[]->l=p->l;

     p->ch[]->r=p->mid;

     p->ch[]=new Tree;

     p->ch[]->l=p->mid+;

     p->ch[]->r=p->r;

     build(p->ch[]);

     build(p->ch[]);

}

void Ins(Tree *p,int  key,int  aim)

{

     Insert(p->root,key);

     if(p->l==p->r)return;

     Ins(p->ch[p->mid<aim],key,aim);

}

int  query_Max(int  l,int  r,int  key,Tree *p)

{

     if(l<=p->l&&p->r<=r)

        return Rank_Max(p->root,key);

     int  tmp=;

     if(l<=p->mid)tmp+=query_Max(l,r,key,p->ch[]);

     if(p->mid<r)tmp+=query_Max(l,r,key,p->ch[]);

     return tmp;

}

int  query_Min(int  l,int  r,int  key,Tree *p)

{

     if(l<=p->l&&p->r<=r)

      return Rank_Min(p->root,key);

     int  tmp=;

     if(l<=p->mid)tmp+=query_Min(l,r,key,p->ch[]);

     if(p->mid<r)tmp+=query_Min(l,r,key,p->ch[]);

     return tmp;

}

void Delete(Tree *p,int  key,int  aim)

{

     Del(p->root,key);

     if(p->l==p->r)return;

     Delete(p->ch[p->mid<aim],key,aim);

}

int main()

{

    //freopen("nt2011_queue.in","r",stdin);

    //freopen("nt2011_queue.out","w",stdout);

    Init();

    scanf("%d",&n);

    root=new Tree;

    root->l=;

    root->r=n;

    build(root);

    for(int  i=;i<=n;i++)

    {

      int x;

      scanf("%d",&x);

      pos[i]=x;

      Ins(root,x,i);

      if(i!=)ans+=query_Max(,i-,x,root);

    }

    scanf("%d",&m);

    for(int i=;i<=m;i++)

    {

      printf("%lld\n",ans);

      int  x,y;

      scanf("%d%d",&x,&y);

      if(x!=) ans-=query_Max(,x-,pos[x],root);

      if(x!=n) ans-=query_Min(x+,n,pos[x],root);

      Delete(root,pos[x],x);

      if(y!=) ans-=query_Max(,y-,pos[y],root);

      if(y!=n) ans-=query_Min(y+,n,pos[y],root);

      Delete(root,pos[y],y);

      swap(pos[x],pos[y]);

      Ins(root,pos[x],x);

      if(x!=) ans+=query_Max(,x-,pos[x],root);

      if(x!=n) ans+=query_Min(x+,n,pos[x],root);

      Ins(root,pos[y],y);

      if(y!=) ans+=query_Max(,y-,pos[y],root);

      if(y!=n) ans+=query_Min(y+,n,pos[y],root);

    }

    printf("%lld\n",ans);

    return ;

}