CF1738D Permutation Addicts

Given a permutation $ a_1, a_2, \dots, a_n $ of integers from $ 1 $ to $ n $ , and a threshold $ k $ with $ 0 \leq k \leq n $ , you compute a sequence $ b_1, b_2, \dots, b_n $ as follows. For every $ 1 \leq i \leq n $ in increasing order, let $ x = a_i $ . - If $ x \leq k $ , set $ b_{x} $ to the last element $ a_j $ ( $ 1 \leq j < i $ ) that $ a_j > k $ . If no such element $ a_j $ exists, set $ b_{x} = n+1 $ . - If $ x > k $ , set $ b_{x} $ to the last element $ a_j $ ( $ 1 \leq j < i $ ) that $ a_j \leq k $ . If no such element $ a_j $ exists, set $ b_{x} = 0 $ . Unfortunately, after the sequence $ b_1, b_2, \dots, b_n $ has been completely computed, the permutation $ a_1, a_2, \dots, a_n $ and the threshold $ k $ are discarded. Now you only have the sequence $ b_1, b_2, \dots, b_n $ . Your task is to find any possible permutation $ a_1, a_2, \dots, a_n $ and threshold $ k $ that produce the sequence $ b_1, b_2, \dots, b_n $ . It is guaranteed that there exists at least one pair of permutation $ a_1, a_2, \dots, a_n $ and threshold $ k $ that produce the sequence $ b_1, b_2, \dots, b_n $ . A permutation of integers from $ 1 $ to $ n $ is a sequence of length $ n $ which contains all integers from $ 1 $ to $ n $ exactly once.

N/A

N/A

For the first test case, permutation $ a = [1,3,2,4] $ and threshold $ k = 2 $ will produce sequence $ b $ as follows. - When $ i = 1 $ , $ x = a_i = 1 \leq k $ , there is no $ a_j $ ( $ 1 \leq j < i $ ) that $ a_j > k $ . Therefore, $ b_1 = n + 1 = 5 $ . - When $ i = 2 $ , $ x = a_i = 3 > k $ , the last element $ a_j $ that $ a_j \leq k $ is $ a_1 $ . Therefore, $ b_3 = a_1 = 1 $ . - When $ i = 3 $ , $ x = a_i = 2 \leq k $ , the last element $ a_j $ that $ a_j > k $ is $ a_2 $ . Therefore, $ b_2 = a_2 = 3 $ . - When $ i = 4 $ , $ x = a_i = 4 > k $ , the last element $ a_j $ that $ a_j \leq k $ is $ a_3 $ . Therefore, $ b_4 = a_3 = 2 $ . Finally, we obtain sequence $ b = [5,3,1,2] $ . For the second test case, permutation $ a = [1,2,3,4,5,6] $ and threshold $ k = 3 $ will produce sequence $ b $ as follows. - When $ i = 1, 2, 3 $ , $ a_i \leq k $ , there is no $ a_j $ ( $ 1 \leq j < i $ ) that $ a_j > k $ . Therefore, $ b_1 = b_2 = b_3 = n + 1 = 7 $ . - When $ i = 4, 5, 6 $ , $ a_i > k $ , the last element $ a_j $ that $ a_j \leq k $ is $ a_3 $ . Therefore, $ b_4 = b_5 = b_6 = a_3 = 3 $ . Finally, we obtain sequence $ b = [7,7,7,3,3,3] $ . For the third test case, permutation $ a = [6,5,4,3,2,1] $ and threshold $ k = 3 $ will produce sequence $ b $ as follows. - When $ i = 1, 2, 3 $ , $ a_i > k $ , there is no $ a_j $ ( $ 1 \leq j < i $ ) that $ a_j \leq k $ . Therefore, $ b_4 = b_5 = b_6 = 0 $ . - When $ i = 4, 5, 6 $ , $ a_i \leq k $ , the last element $ a_j $ that $ a_j > k $ is $ a_3 $ . Therefore, $ b_1 = b_2 = b_3 = a_3 = 4 $ . Finally, we obtain sequence $ b = [4,4,4,0,0,0] $ .