{"problem":{"name":"Circular Addition","description":{"content":"We have an integer sequence of length $N$: $x=(x_0,x_1,\\cdots,x_{N-1})$ (note that its index is $0$\\-based). Initially, all elements of $x$ are $0$. You can repeat the following operation any number o","description_type":"Markdown"},"platform":"AtCoder","limit":{"time_limit":2000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"arc136_c"},"statements":[{"statement_type":"Markdown","content":"We have an integer sequence of length $N$: $x=(x_0,x_1,\\cdots,x_{N-1})$ (note that its index is $0$\\-based). Initially, all elements of $x$ are $0$.\nYou can repeat the following operation any number of times.\n\n*   Choose integers $i,k$ ($0 \\leq i \\leq N-1$, $1 \\leq k \\leq N$). Then, for every $j$ such that $i \\leq j \\leq i+k-1$, increase the value of $x_{j\\bmod N}$ by $1$.\n\nYou are given an integer sequence of length $N$: $A=(A_0,A_1,\\cdots,A_{N-1})$. Find the minimum number of operations needed to make $x$ equal $A$.\n\n## Constraints\n\n*   $1 \\leq N \\leq 200000$\n*   $1 \\leq A_i \\leq 10^9$\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$A_0$ $A_1$ $\\cdots$ $A_{N-1}$\n\n[samples]","is_translate":false,"language":"English"}],"meta":{"iden":"arc136_c","tags":[],"sample_group":[["4\n1 2 1 2","2\n\nWe should do the following.\n\n*   Initially, we have $x=(0,0,0,0)$.\n*   Do the operation with $i=1,k=3$, making $x=(0,1,1,1)$.\n*   Do the operation with $i=3,k=3$, making $x=(1,2,1,2)$."],["5\n3 1 4 1 5","7"],["1\n1000000000","1000000000"]],"created_at":"2026-03-03 11:01:13"}}