{"problem":{"name":"B. Shift and Push","description":{"content":"Given two equally sized arrays A and B of size N. A is empty and B has some values. You need to fill A with an element X such that X belongs to B. The only operations allowed are: 1. Copy B[i] to A","description_type":"Markdown"},"platform":"Codeforces","limit":{"time_limit":1000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"CF10105B"},"statements":[{"statement_type":"Markdown","content":"Given two equally sized arrays A and B of size N. A is empty and B has some values.\n\nYou need to fill A with an element X such that X belongs to B.\n\nThe only operations allowed are:\n\n1. Copy B[i] to A[i].\n\n2. Cyclic shift B by 1 to the the right.\n\nYou need to minimise the number of operations.\n\nThe first line contains a single positive integer N(1 ≤ N ≤ 106), denoting the size of the arrays.\n\nNext line contains N space separated positive integers denoting the elements of the array B(1 ≤ B[i ≤ 105)].\n\nOutput a single integer, denoting the minimum number of operations required.\n\nIn the first test case:\n\nWe can have 5 steps as: fill first element, shift, fill second element, shift, fill third element.\n\nInitially, A = [_, _, _, B = [1, 2, 3]]\n\nAfter step 1, A = [1, _, _, B = [1, 2, 3]]\n\nAfter step 2, A = [1, _, _, B = [3, 1, 2]]\n\nAfter step 3, A = [1, 1, _, B = [3, 1, 2]]\n\nAfter step 4, A = [1, 1, _, B = [2, 3, 1]]\n\nAfter step 5, A = [1, 1, 1, B = [2, 3, 1]]\n\n## Input\n\nThe first line contains a single positive integer N(1 ≤ N ≤ 106), denoting the size of the arrays.Next line contains N space separated positive integers denoting the elements of the array B(1 ≤ B[i ≤ 105)].\n\n## Output\n\nOutput a single integer, denoting the minimum number of operations required.\n\n[samples]\n\n## Note\n\nIn the first test case:We can have 5 steps as: fill first element, shift, fill second element, shift, fill third element.Initially, A = [_, _, _, B = [1, 2, 3]]After step 1, A = [1, _, _, B = [1, 2, 3]]After step 2, A = [1, _, _, B = [3, 1, 2]]After step 3, A = [1, 1, _, B = [3, 1, 2]]After step 4, A = [1, 1, _, B = [2, 3, 1]]After step 5, A = [1, 1, 1, B = [2, 3, 1]]","is_translate":false,"language":"English"},{"statement_type":"Markdown","content":"**Definitions**  \nLet $ N \\in \\mathbb{Z}^+ $ be the size of arrays $ A $ and $ B $.  \nLet $ B = (b_0, b_1, \\dots, b_{N-1}) $ be the initial array of integers.  \nArray $ A $ is initially empty: $ A = (\\bot, \\bot, \\dots, \\bot) $.  \n\nA **copy operation** at index $ i $ sets $ A[i] = B[i] $.  \nA **right cyclic shift** transforms $ B $ into $ (b_{N-1}, b_0, b_1, \\dots, b_{N-2}) $.  \n\n**Constraints**  \n1. $ 1 \\leq N \\leq 10^6 $  \n2. $ 1 \\leq b_i \\leq 10^5 $ for all $ i \\in \\{0, 1, \\dots, N-1\\} $  \n\n**Objective**  \nMinimize the total number of operations (copy + shift) required to make $ A[i] = x $ for all $ i $, for some $ x \\in B $.  \n\nFor each candidate value $ x \\in B $, let $ S_x = \\{ i \\in \\{0, \\dots, N-1\\} \\mid b_i = x \\} $ be the set of indices where $ x $ appears in $ B $.  \nFor each $ i \\in S_x $, the number of right shifts needed to align $ b_i $ to position $ j $ is $ (j - i) \\mod N $.  \nTo fill $ A[j] = x $, we must perform $ k $ shifts and one copy at the moment $ x $ is at position $ j $.  \n\nThe minimal operations to fill all positions with $ x $ is:  \n$$\n\\min_{\\text{order of filling}} \\left( \\text{number of shifts} + |S_x| \\right)\n$$  \nwhere the shifts are minimized by optimally ordering the copy operations.  \n\nFor fixed $ x $, the minimal total operations is:  \n$$\n|S_x| + \\min_{\\sigma \\in \\text{Perms}(S_x)} \\sum_{k=1}^{|S_x|} \\left( \\sigma(k) - \\sigma(k-1) \\right) \\mod N\n$$  \nwhere $ \\sigma(0) = 0 $, and $ \\sigma $ is the order of indices in $ S_x $ to copy.  \n\nEquivalently, the minimal shifts needed to cover all positions in $ S_x $ in cyclic order is:  \n$$\nN - \\max_{i,j \\in S_x} \\left( (j - i) \\mod N \\right)\n$$  \nBut more directly: the minimal number of shifts is $ N - d_{\\max} $, where $ d_{\\max} $ is the maximum gap between consecutive occurrences of $ x $ in the circular array.  \n\nThus, for each $ x \\in B $, define:  \n- Let $ \\text{positions}_x = \\{ i_0, i_1, \\dots, i_{m-1} \\} $, sorted, $ m = |S_x| $.  \n- Compute gaps: $ g_k = (i_{k} - i_{k-1}) \\mod N $ for $ k = 1, \\dots, m $, with $ i_{-1} = i_{m-1} - N $.  \n- Let $ g_{\\max} = \\max_k g_k $.  \n- Then operations for $ x $: $ N - g_{\\max} + m $.  \n\n**Final Objective**  \n$$\n\\min_{x \\in B} \\left( N - g_{\\max}^{(x)} + |S_x| \\right)\n$$","is_translate":false,"language":"Formal"}],"meta":{"iden":"CF10105B","tags":[],"sample_group":[],"created_at":"2026-03-03 11:00:39"}}