class UnionFind {
    public int[] p;

    public UnionFind(int size)
    {
        p = new int[size];
        for(int i = 0; i < size; i ++ )
            p[i] = i;
    }

    public int find(int x)
    {
        if(p[x] != x) p[x] = find(p[x]);
        return p[x];
    }
}

class Solution {
    public int[] shortestDistanceAfterQueries(int n, int[][] queries) {
        UnionFind uf = new UnionFind(n - 1);
        int[] ans = new int[queries.length];
        int cnt = n - 1;

        for(int qi = 0; qi < queries.length; qi ++ )
        {
            int l = queries[qi][0];
            int r = queries[qi][1] - 1;
            int pr = uf.find(r);
            for(int i = uf.find(l); i < r; i = uf.find(i + 1))
            {
                uf.p[i] = pr;
                cnt -- ;
            }
            ans[qi] = cnt;
        }

        return ans;
    }
}