{"raw_statement":[{"iden":"problem statement","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."},{"iden":"constraints","content":"*   $2 \\leq N \\leq 5000$\n*   $\\lvert A_i \\rvert \\leq 10^9$\n*   All input values are integers."},{"iden":"input","content":"The input is given from Standard Input in the following format:\n\n$N$\n$A_1$ $A_2$ $\\ldots$ $A_N$"},{"iden":"sample input 1","content":"3\n2 7 6"},{"iden":"sample output 1","content":"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$."},{"iden":"sample input 2","content":"3\n-2 -5 -2"},{"iden":"sample output 2","content":"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$."},{"iden":"sample input 3","content":"5\n1 1 1 1 -7"},{"iden":"sample output 3","content":"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$."}],"translated_statement":null,"sample_group":[],"show_order":["default"],"formal_statement":null,"simple_statement":null,"has_page_source":true}