{"problem":{"name":"Sorting Color Balls","description":{"content":"There are $N$ balls arranged from left to right. The color of the $i$\\-th ball from the left is Color $C_i$, and an integer $X_i$ is written on it. Takahashi wants to rearrange the balls so that the i","description_type":"Markdown"},"platform":"AtCoder","limit":{"time_limit":3000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"abc261_f"},"statements":[{"statement_type":"Markdown","content":"There are $N$ balls arranged from left to right. The color of the $i$\\-th ball from the left is Color $C_i$, and an integer $X_i$ is written on it.\nTakahashi wants to rearrange the balls so that the integers written on the balls are non-decreasing from left to right. In other words, his objective is to reach a situation where, for every $1\\leq i\\leq N-1$, the number written on the $(i+1)$\\-th ball from the left is greater than or equal to the number written on the $i$\\-th ball from the left.\nFor this, Takahashi can repeat the following operation any number of times (possibly zero):\n\n> Choose an integer $i$ such that $1\\leq i\\leq N-1$.  \n> If the colors of the $i$\\-th and $(i+1)$\\-th balls from the left are different, pay a cost of $1$. (No cost is incurred if the colors are the same).  \n> Swap the $i$\\-th and $(i+1)$\\-th balls from the left.\n\nFind the minimum total cost Takahashi needs to pay to achieve his objective.\n\n## Constraints\n\n*   $2 \\leq N \\leq 3\\times 10^5$\n*   $1\\leq C_i\\leq N$\n*   $1\\leq X_i\\leq N$\n*   All values in input are integers.\n\n## Input\n\nInput is given from Standard Input in the following format:\n\n$N$\n$C_1$ $C_2$ $\\ldots$ $C_N$\n$X_1$ $X_2$ $\\ldots$ $X_N$\n\n[samples]","is_translate":false,"language":"English"}],"meta":{"iden":"abc261_f","tags":[],"sample_group":[["5\n1 5 2 2 1\n3 2 1 2 1","6\n\nLet us represent a ball as $($Color$,$ Integer$)$. The initial situation is $(1,3)$, $(5,2)$, $(2,1)$, $(2,2)$, $(1,1)$. Here is a possible sequence of operations for Takahashi:\n\n*   Swap the $1$\\-st ball (Color $1$) and $2$\\-nd ball (Color $5$). Now the balls are arranged in the order $(5,2)$, $(1,3)$, $(2,1)$, $(2,2)$, $(1,1)$.\n*   Swap the $2$\\-nd ball (Color $1$) and $3$\\-rd ball (Color $2$). Now the balls are arranged in the order $(5,2)$, $(2,1)$, $(1,3)$, $(2,2)$, $(1,1)$.\n*   Swap the $3$\\-rd ball (Color $1$) and $4$\\-th ball (Color $2$). Now the balls are in the order $(5,2)$, $(2,1)$, $(2,2)$, $(1,3)$, $(1,1)$.\n*   Swap the $4$\\-th ball (Color $1$) and $5$\\-th ball (Color $1$). Now the balls are in the order $(5,2)$, $(2,1)$, $(2,2)$, $(1,1)$, $(1,3)$.\n*   Swap the $3$\\-rd ball (Color $2$) and $4$\\-th ball (Color $1$). Now the balls are in the order$(5,2)$, $(2,1)$, $(1,1)$, $(2,2)$, $(1,3)$.\n*   Swap the $1$\\-st ball (Color $5$) and $2$\\-nd ball (Color $2$). Now the balls are in the order $(2,1)$, $(5,2)$, $(1,1)$, $(2,2)$, $(1,3)$.\n*   Swap the $2$\\-nd ball (Color $5$) and $3$\\-rd ball (Color $1$). Now the balls are in the order $(2,1)$, $(1,1)$, $(5,2)$, $(2,2)$, $(1,3)$.\n\nAfter the last operation, the numbers written on the balls are $1,1,2,2,3$ from left to right, which achieves Takahashi's objective.\nThe $1$\\-st, $2$\\-nd, $3$\\-rd, $5$\\-th, $6$\\-th, and $7$\\-th operations incur a cost of $1$ each, for a total of $6$, which is the minimum. Note that the $4$\\-th operation does not incur a cost since the balls are both in Color $1$."],["3\n1 1 1\n3 2 1","0\n\nAll balls are in the same color, so no cost is incurred in swapping balls."],["3\n3 1 2\n1 1 2","0\n\nTakahashi's objective is already achieved without any operation."]],"created_at":"2026-03-03 11:01:14"}}