#include<set>
#include <unordered_set>
#include <unordered_map>
#include<map>
#include<list>
#include<iomanip>
#include<cmath>
#include<string>
#include<vector>
#include<queue>
#include<stack>
#include<complex>
#include<sstream>
#include<iostream>
#include<fstream>
#include<algorithm>
#include<numeric>
#include<utility>
#include<functional>
#include<stdio.h>
#include<assert.h>
#include<memory.h>
#include<bitset>
#include<math.h>
#include <string.h>
#include <strings.h>


#define f first
#define s second
#define mp make_pair
#define pb push_back
#define lp(i,a,n) for(int i=(a);i<=(int)(n);++i)
#define lpd(i,a,n) for(int i=(a);i>=(int)(n);--i)
#define clr(a,b) memset(a,b,sizeof a)
#define all(v) v.begin(),v.end()
#define println(a) cout <<(a) <<endl
#define sz(x) ((int)(x).size())
#define readi(x) scanf("%d",&x)
#define read2i(x,y) scanf("%d%d",&x,&y)
#define read3i(x,y,z) scanf("%d%d%d",&x,&y,&z)
#define readll(x) scanf("%I64d",&x)
#define mod 1000000007
#define eps 1e-10
#define infi  1000000000ll
#define infll 1000000000000000000ll


using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<ll> vll;
typedef set<int> si;
typedef unordered_set<int> usi;
typedef map<int,int> mii;
typedef map<ll,ll> mll;
typedef unordered_map<ll,ll> umll;

const int N = 250005 , A = 50002;

int n,q,a[N],tree[2][A],x[N],y[N],lastEdit[N];
vector<pii> qIndex[N];
pii queriesAns[N],curArr[N];
struct query {
    int cur,prev,i;
};
vector<query> prevQueries;

void update(int i,int diff,int tree[]) {
    while (i < A) tree[i] += diff , i += i&-i;
}

int getSum (int i,int tree[]) {
    int ret = 0;
    while (i > 0) ret += tree[i] , i -= i&-i;
    return ret;
}

int main(){
    scanf("%d",&n);
    lp(i, 1, n) scanf("%d",&a[i]),update(a[i], 1, tree[0]);

    scanf("%d",&q);
    lp(i, 1, q) {
        scanf("%d%d",&x[i],&y[i]);
        qIndex[x[i]].pb({y[i],i});
    }

    ll ans = 0;

    lpd(i, n, 1) {
        update(a[i], -1, tree[0]);

        curArr[i] = {getSum(A-2,tree[0])-getSum(a[i], tree[0]),getSum(a[i]-1, tree[1])};

        for(pii x:qIndex[i])
            queriesAns[x.s] = {getSum(A-2, tree[0])-getSum(x.f, tree[0]),getSum(x.f-1, tree[1])};

        ans += curArr[i].s;
        update(a[i], 1, tree[1]);
    }

    lp(i, 1, q) {

//        lp(j, 0, sz(prevQueries)-1) if(prevQueries[j].i == x[i]) {
//            prevQueries.erase(prevQueries.begin()+j);
//            break;
//        }

        pii &temp1 = curArr[x[i]], &temp2 = queriesAns[i];

        lp(j, 0 , sz(prevQueries)-1) {
            query q = prevQueries[j];
            if(q.i > x[i]) {
                if(q.prev < a[x[i]] && q.cur >= a[x[i]] && j >= lastEdit[x[i]]) -- curArr[x[i]].s;
                if(q.prev < y[i] && q.cur >= y[i]) -- queriesAns[i].s;

                if(q.prev >= a[x[i]] && q.cur < a[x[i]] && j >= lastEdit[x[i]]) ++ curArr[x[i]].s;
                if(q.prev >= y[i] && q.cur < y[i]) ++ queriesAns[i].s;

            } else if(q.i < x[i]){

                if(q.prev > a[x[i]] && q.cur <= a[x[i]] && j >= lastEdit[x[i]]) -- curArr[x[i]].f;
                if(q.prev > y[i] && q.cur <= y[i]) -- queriesAns[i].f;

                if(q.prev <= a[x[i]] && q.cur > a[x[i]] && j >= lastEdit[x[i]]) ++ curArr[x[i]].f;
                if(q.prev <= y[i] && q.cur > y[i]) ++ queriesAns[i].f;

            }
        }

        ans += queriesAns[i].f-curArr[x[i]].f + queriesAns[i].s-curArr[x[i]].s;

        printf("%lld\n",ans);
        curArr[x[i]] = queriesAns[i];
        prevQueries.pb({y[i],a[x[i]],x[i]});
        a[x[i]] = y[i];
        lastEdit[x[i]] = i;
    }

    return 0;
}



/*
 */

//ios::sync_with_stdio(0);cin.tie(0);