#include<iostream>
#include<cmath>
#include<vector>
using namespace std;
#define SQRMX 501
#define NMMX 50001
int sqr,n,nsqr;
long long tree[SQRMX+1][NMMX+1]={0};
vector <int> a[SQRMX+1];
int ready(int x, long long t[]){
    long long s=0;
    while(x){
    s+=t[x];
    x-=(x & -x);
    }
    return s;
}
int read(int x,int y){
    long long s=0;
    while(x){
        s+=ready(y,tree[x]);
        x-=(x & -x);
    }
    return s;
}
void updatey(int x, long long t[],int val){
    while(x<=NMMX)
    {
        t[x]+=val;
        x+=(x & -x);
    }
}
void update(int x,int y,int val){
    while(x<=SQRMX){
        updatey(y,tree[x],val);
        x+=(x&-x);
    }
}
long long tot;
void upd(int idx, int val){
    idx--;int x=idx/sqr;
    idx-=(x*sqr);

    x++;

    tot-=read(x-1,NMMX)-read(x-1,a[x][idx])+read(nsqr,a[x][idx]-1)-read(x,a[x][idx]-1);
    for(int i=0;i<idx;++i)
        if(a[x][i]>a[x][idx])--tot;
    for(int i=idx+1; i<a[x].size();++i)
        if(a[x][i]<a[x][idx])--tot;
    update(x,a[x][idx],-1);
    a[x][idx]=val;
    tot+=read(x-1,NMMX)-read(x-1,a[x][idx])+read(nsqr,a[x][idx]-1)-read(x,a[x][idx]-1);
    for(int i=0;i<idx;++i)
        if(a[x][i]>a[x][idx])++tot;
    for(int i=idx+1;i<a[x].size();++i)
        if(a[x][i]<a[x][idx])++tot;
    update(x,a[x][idx],1);
}
int main(){
    int n;
    scanf("%d",&n);
    sqr=sqrt(n);
    //if(n==1)
    //exit(1);
    int tmp;
    tot=0;
    nsqr=1;
    for(int i=0,c=0;i<n;++i,++c){
        if(c==sqr)
            nsqr++,c=0;
        scanf("%d",&tmp);
        a[nsqr].push_back(tmp);
        tot+=read(nsqr,NMMX)-read(nsqr,tmp);
        update(nsqr,tmp,1);
    }
    int m;
    scanf("%d",&m);
    int u,v;
    while(m--){
        scanf("%d%d",&u,&v);
        upd(u,v);
        printf("%lld\n",tot);
    }
    //system("pause");
}