201362: [AtCoder]ARC136 C - Circular Addition

Memory Limit:1024 MB Time Limit:2 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

Score : $500$ points

Problem Statement

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 of times.

  • 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$.

You 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$.

Constraints

  • $1 \leq N \leq 200000$
  • $1 \leq A_i \leq 10^9$
  • All values in input are integers.

Input

Input is given from Standard Input in the following format:

$N$
$A_0$ $A_1$ $\cdots$ $A_{N-1}$

Output

Print the answer.


Sample Input 1

4
1 2 1 2

Sample Output 1

2

We should do the following.

  • Initially, we have $x=(0,0,0,0)$.
  • Do the operation with $i=1,k=3$, making $x=(0,1,1,1)$.
  • Do the operation with $i=3,k=3$, making $x=(1,2,1,2)$.

Sample Input 2

5
3 1 4 1 5

Sample Output 2

7

Sample Input 3

1
1000000000

Sample Output 3

1000000000

Input

题意翻译

你有一个长度为 $n$ 的序列 $x$,其中元素由 $0$ 到 $n-1$编号。序列各元素初始全为 $0$。 你可以进行若干次如下操作:每次操作选取一组 $i$ 和 $k$ $(0 \leq i \leq n - 1, 1 \leq k \leq n)$,对所有满足 $i \leq j \leq i + 1$ 的 $j$,执行 $x_{j \bmod n} \leftarrow x_{j \bmod n} + 1$。 (通俗地讲就是将序列首尾相接拼成一个环,每次选取环上的一段,将其上元素的值全部加 $1$。) 现给定另一个序列 $A$,求出由 $x$ 变换为 $A$ 所需的最小操作数。

加入题单

上一题 下一题 算法标签: