CF1375H Set Merging

You are given a permutation $ a_1, a_2, \dots, a_n $ of numbers from $ 1 $ to $ n $ . Also, you have $ n $ sets $ S_1,S_2,\dots, S_n $ , where $ S_i=\{a_i\} $ . Lastly, you have a variable $ cnt $ , representing the current number of sets. Initially, $ cnt = n $ . We define two kinds of functions on sets: $ f(S)=\min\limits_{u\in S} u $ ; $ g(S)=\max\limits_{u\in S} u $ . You can obtain a new set by merging two sets $ A $ and $ B $ , if they satisfy $ g(A)

N/A

N/A

In the first sample: We have $ S_1=\{1\},S_2=\{3\},S_3=\{2\} $ initially. In the first operation, because $ g(S_3)=2