#include <bits/stdc++.h>
using namespace std;

#define pi pair<int, int>
#define inf32 0x3f3f3f3f
#define inf64 0x3f3f3f3f3f3f3f3f
#define all(x) x.begin(), x.end()
#define Unique(v) v.erase(unique(all(v)), v.end());
#define int long long
#define setinf(d) memset(d, inf32, sizeof d)
#define setneg(d) memset(d, -1, sizeof d)
#define set0(d) memset(d, 0, sizeof d)
#define Log2(x) 63 - __builtin_clzll(x)
#define oo 2e18
#define mod 1000000007
#define FILENAME "f"

const int maxn = 1e5 + 5;
int n;
int a[maxn];
set<int> s[maxn];

signed main(){
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);

    cin >> n;
    int cur = 0;
    for(int i = 1; i <= n; i++){
        cur += i * (n + 1 - i);
    }

    for(int i = 1; i <= 1e5; i++) s[i].insert(0), s[i].insert(n + 1);

    for(int i = 1; i <= n; i++){
        cin >> a[i];
        s[a[i]].insert(i);
        auto it = s[a[i]].find(i);
        //if(it == ++s[a[i]].begin()) continue;
        auto prv = prev(it),  nx = next(it);
        cur -= (*prv) * (*nx - i);
    }

    int q;
    cin >> q;
    while(q--){
        int i, x;
        cin >> i >> x;
        auto it = s[a[i]].find(i);
        auto prv = prev(it), nx = next(it);
        cur += *prv * (n + 1 - i);
        if(nx != --s[a[i]].end()){
            auto nxnx = next(nx);
            cur += i * (n + 1 - *nx);
            cur -= *prv * (n + 1 - *nx);
        }
        s[a[i]].erase(i);
        a[i] = x;

        s[a[i]].insert(i);
        it = s[a[i]].find(i);
        prv = prev(it), nx = next(it);
        cur -= *prv * (n + 1 - i);
        if(nx != --s[a[i]].end()){
            auto nxnx = next(nx);
            cur -= i * (n + 1 - *nx);
            cur += *prv * (n + 1  - *nx);
        }

        cout << cur << '\n';
    }
}