{"problem":{"name":"Make Adjacent","description":{"content":"An integer sequence of length $2n$, $X=(X_1,X_2,\\dots,X_{2n})$, such that $X_{2i-1}=X_{2i}$ for every $i=1,2,\\dots,n$ is called a **good sequence**. There is an integer sequence of length $2N$, $A=(A_","description_type":"Markdown"},"platform":"AtCoder","limit":{"time_limit":2000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"arc165_f"},"statements":[{"statement_type":"Markdown","content":"An integer sequence of length $2n$, $X=(X_1,X_2,\\dots,X_{2n})$, such that $X_{2i-1}=X_{2i}$ for every $i=1,2,\\dots,n$ is called a **good sequence**.\nThere is an integer sequence of length $2N$, $A=(A_1,A_2,\\dots,A_{2N})$, which contains each integer $i=1,2,\\dots,N$ exactly twice.\nWe want to make $A$ a **good sequence** by performing the operation of swapping the values of two adjacent terms zero or more times.\nLet $K$ be the minimum number of operations we must perform the operation to make $A$ a **good sequence**. Find the lexicographically smallest **good sequence** that can be obtained by performing the operations $K$ times on $A$.\nWhat is lexicographical order on sequences?A sequence $S = (S_1,S_2,\\ldots,S_{|S|})$ is **lexicographically smaller** than $T = (T_1,T_2,\\ldots,T_{|T|})$ when 1. or 2. below holds. Here, $|S|$ and $|T|$ denotes the lengths of $S$ and $T$, respectively.\n\n1.  $|S| \\lt |T|$ and $(S_1,S_2,\\ldots,S_{|S|}) = (T_1,T_2,\\ldots,T_{|S|})$.\n2.  There is an integer $1 \\leq i \\leq \\min\\lbrace |S|, |T| \\rbrace$ that satisfy both of the following:\n    *   $(S_1,S_2,\\ldots,S_{i-1}) = (T_1,T_2,\\ldots,T_{i-1})$.\n    *   $S_i$ is smaller than $T_i$ (as a number).\n\n## Constraints\n\n*   $1 \\leq N \\leq 2 \\times 10^5$\n*   $1 \\leq A_i \\leq N$\n*   $A$ contains each integer $i=1,2,\\dots,N$ exactly twice.\n*   All input values are integers.\n\n## Input\n\nThe input is given from Standard Input in the following format:\n\n$N$\n$A_1$ $A_2$ $\\dots$ $A_{2N}$\n\n[samples]","is_translate":false,"language":"English"}],"meta":{"iden":"arc165_f","tags":[],"sample_group":[["3\n3 2 1 2 3 1","2 2 3 3 1 1\n\nFor example, we can perform the operation four times as $(3,2,1,2,3,1) \\rightarrow (3,2,1,3,2,1) \\rightarrow (3,2,3,1,2,1) \\rightarrow (3,3,2,1,2,1) \\rightarrow (3,3,2,2,1,1)$ to make $A$ a **good sequence**. This number is the minimum needed. With four operations, we can also make $A=(2,2,3,3,1,1)$, and the answer is $(2,2,3,3,1,1)$."],["3\n1 1 2 2 3 3","1 1 2 2 3 3"],["15\n15 12 11 10 5 11 13 2 6 14 3 6 5 14 10 15 1 2 13 9 7 4 9 1 3 8 12 4 8 7","11 11 5 5 6 6 10 10 14 14 15 15 2 2 12 12 13 13 1 1 3 3 9 9 4 4 7 7 8 8"]],"created_at":"2026-03-03 11:01:13"}}