const int N=100005;
int parent[N],ma[N],siz[N];
#define ll long long
int find(int v)
{
    if(v==parent[v]) return v;
    return parent[v]=find(parent[v]);
}
void uni(int a,int b)
{
    if(siz[a]<siz[b]) swap(a,b);
    siz[a]+=siz[b];
    parent[b]=a;
    ma[a]=max(a,b);
    ma[b]=ma[a];
    return ;
}
vector<int> fun(int n,vector<int> v1,vector<int> v2)
{
    ll last=((n)*(n+1))/2;
    for(int i=1;i<=n;i++)
    {
        parent[i]=i;
        siz[i]=1;
        ma[i]=i;
    }
    vector<int> ans;
    int m=v1.size();
    for(int i=0;i<m;i++)
    {
        int a=find(v1[i]),b=find(v2[i]);
        if(a!=b)
        {
            last-=ma[a];
            last-=ma[b];
            uni(a,b);
            last+=ma[find(a)];
        }
        ans.push_back(last);
    }
    return ans;
}