{"problem":{"name":"Almost Bubble Sort","description":{"content":"You are given a permutation $P=(P_1,P_2,\\cdots,P_N)$ of $(1,2,\\cdots,N)$. You want to perform zero or more swaps of adjacent elements so that $P$ satisfies the following condition: *   The number of ","description_type":"Markdown"},"platform":"AtCoder","limit":{"time_limit":10000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"awtf2024_d"},"statements":[{"statement_type":"Markdown","content":"You are given a permutation $P=(P_1,P_2,\\cdots,P_N)$ of $(1,2,\\cdots,N)$.\nYou want to perform zero or more swaps of adjacent elements so that $P$ satisfies the following condition:\n\n*   The number of indices $i$ such that $P_i > P_{i+1}$ is at most $1$.\n\nFind the minimum number of swaps required.\n\n## Constraints\n\n*   $2 \\leq N \\leq 800000$\n*   $(P_1,P_2,\\cdots,P_N)$ is a permutation of $(1,2,\\cdots,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$ $\\cdots$ $P_N$\n\n[samples]","is_translate":false,"language":"English"}],"meta":{"iden":"awtf2024_d","tags":[],"sample_group":[["3\n3 2 1","1\n\nSwapping $P_1$ and $P_2$ turns $P$ into $(2,3,1)$, which satisfies the condition."],["4\n2 4 1 3","0"],["6\n2 3 1 6 4 5","1"],["20\n8 13 6 11 20 3 12 18 17 4 10 1 7 16 19 5 2 15 14 9","36"]],"created_at":"2026-03-03 11:01:13"}}