{"problem":{"name":"Approximate Equalization","description":{"content":"You are given an integer sequence of length $N$: $A=(A_1,A_2,\\ldots,A_N)$. Takahashi can perform the following two operations any number of times, possibly zero, in any order. *   Choose an integer $","description_type":"Markdown"},"platform":"AtCoder","limit":{"time_limit":2000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"abc307_g"},"statements":[{"statement_type":"Markdown","content":"You are given an integer sequence of length $N$: $A=(A_1,A_2,\\ldots,A_N)$.\nTakahashi can perform the following two operations any number of times, possibly zero, in any order.\n\n*   Choose an integer $i$ such that $1\\leq i\\leq N-1$, and decrease $A_i$ by $1$ and increase $A_{i+1}$ by $1$.\n*   Choose an integer $i$ such that $1\\leq i\\leq N-1$, and increase $A_i$ by $1$ and decrease $A_{i+1}$ by $1$.\n\nFind the minimum number of operations required to make the sequence $A$ satisfy the following condition:\n\n*   $\\lvert A_i-A_j\\rvert\\leq 1$ for any pair $(i,j)$ of integers between $1$ and $N$, inclusive.\n\n## Constraints\n\n*   $2 \\leq N \\leq 5000$\n*   $\\lvert A_i \\rvert \\leq 10^9$\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$ $\\ldots$ $A_N$\n\n[samples]","is_translate":false,"language":"English"}],"meta":{"iden":"abc307_g","tags":[],"sample_group":[["3\n2 7 6","4\n\nYou can make $A$ satisfy the condition with four operations as follows.\n\n*   Choose $i=1$, and increase $A_1$ by $1$ and decrease $A_2$ by $1$, making $A=(3,6,6)$.\n*   Choose $i=1$, and increase $A_1$ by $1$ and decrease $A_2$ by $1$, making $A=(4,5,6)$.\n*   Choose $i=2$, and increase $A_2$ by $1$ and decrease $A_3$ by $1$, making $A=(4,6,5)$.\n*   Choose $i=1$, and increase $A_1$ by $1$ and decrease $A_2$ by $1$, making $A=(5,5,5)$.\n\nThis is the minimum number of operations required, so print $4$."],["3\n-2 -5 -2","2\n\nYou can make $A$ satisfy the condition with two operations as follows:\n\n*   Choose $i=1$, and decrease $A_1$ by $1$ and increase $A_2$ by $1$, making $A=(-3,-4,-2)$.\n*   Choose $i=2$, and increase $A_2$ by $1$ and decrease $A_3$ by $1$, making $A=(-3,-3,-3)$.\n\nThis is the minimum number of operations required, so print $2$."],["5\n1 1 1 1 -7","13\n\nBy performing the operations appropriately, with $13$ operations you can make $A=(0,0,-1,-1,-1)$, which satisfies the condition in the problem statement. It is impossible to satisfy it with $12$ or fewer operations, so print $13$."]],"created_at":"2026-03-03 11:01:14"}}