{"problem":{"name":"Minimum Cost Sort","description":{"content":"You are given a permutation $P = (P_1, P_2, \\ldots, P_N)$ of $(1, 2, \\ldots, N)$. Takahashi can repeatedly perform the following operation on $P$ (possibly zero times): *   Choose an integer $i$ sati","description_type":"Markdown"},"platform":"AtCoder","limit":{"time_limit":2000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"arc194_b"},"statements":[{"statement_type":"Markdown","content":"You are given a permutation $P = (P_1, P_2, \\ldots, P_N)$ of $(1, 2, \\ldots, N)$. Takahashi can repeatedly perform the following operation on $P$ (possibly zero times):\n\n*   Choose an integer $i$ satisfying $1 \\leq i \\leq N-1$. Pay a cost of $i$, and swap $P_i$ and $P_{i+1}$.\n\nFind the minimum total cost required to sort $P$ in ascending order.\n\n## Constraints\n\n*   $2 \\leq N \\leq 2 \\times 10^5$\n*   $(P_1, P_2, \\ldots, P_N)$ is a permutation of $(1, 2, \\ldots, N)$.\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$P_1$ $P_2$ $\\ldots$ $P_N$\n\n[samples]","is_translate":false,"language":"English"}],"meta":{"iden":"arc194_b","tags":[],"sample_group":[["3\n3 2 1","4\n\nTakahashi can sort $P$ in ascending order as follows:\n\n*   Pay a cost of $1$ and swap $P_1 = 3$ and $P_2 = 2$. Now, $P = (2, 3, 1)$.\n*   Pay a cost of $2$ and swap $P_2 = 3$ and $P_3 = 1$. Now, $P = (2, 1, 3)$.\n*   Pay a cost of $1$ and swap $P_1 = 2$ and $P_2 = 1$. Now, $P = (1, 2, 3)$.\n\nThe total cost for these operations is $4$, which is the minimum possible."],["5\n2 4 1 3 5","6"],["2\n1 2","0"]],"created_at":"2026-03-03 11:01:14"}}