サンプル1(出力例1の下にある)図を右からやっていく形

連結成分を数えるint cnt = 0;と
解答用の配列vector<int>ans;
を用意しておいて

• 一番右は頂点無しなのでansに0を挿入
• 次は頂点6が一個加わるのでcntに1を足しansにcntを挿入
• 頂点5以降だが、まず頂点が一つふえるのでとりあえずcntに1つ足す。現在の頂点より大きい頂点と今まで連結しておらず新規に連結するようだったら連結成分が減るのでcntから1引く。 その後ansにcntを挿入する

連結してるかどうかの判定はUnionFindを使えばよい。

ansは順番が逆になっているので、C++であればreverseで順番を戻して出力

解答例（C++)
https://atcoder.jp/contests/abc229/submissions/27568298