题目描述

有一个长度为 \(N\) 的整数序列 \(X=(x[0],x[1],…,x[N-1])\)，起初这个序列的元素都为 \(0\)。

你可以重复以下操作：

选择整数 \(i\) 和 \(k（0≤i≤N-1, 1≤k≤N）\)，然后对于每一个 \(j（i≤j≤i+k-1）\)，将 \(x[j~mod~N]\) 的值加 \(1\)。

给你一个长度为 \(N\) 的整数序列 \(A=(a[0],a[1],…,a[N-1])\)，找出使得 \(X\) 等于 \(A\) 所需的最小操作次数。

格式

输入格式

第一行一个正整数 \(N（1≤N≤2×10^5）\)；

第二行 \(N\) 个正整数表示 \(A\) 序列，以空格隔开。\(（1≤a[i]≤10^9）\)

输出格式

输出一个正整数，表示最少操作次数。

样例1

样例输入1

5
3 1 4 1 5

样例输出1

7

样例解释

前两步选择 \(i=4,j=2\)，使得序列 \(X=(20002)\)；

第三步选择 \(i=4,j=4\)，使得序列 \(X=(31103)\)；

第四步选择 \(i=2,j=3\)，使得序列 \(X=(31214)\)；

第五步选择 \(i=4,j=1\)，使得序列 \(X=(31215)\)；

第六、七步选择 \(i=2,j=1\)，使得序列 \(X=(31415)\)；

限制

时间：\(1s\) 空间：\(128M\)

对于 \(10\%\) 的数据：\(1≤N≤10\)；\(A\) 序列元素值成单峰；

另 \(20\%\) 的数据：\(1≤N≤20\)；\(A\) 序列元素值成双峰；

对于 \(100\%\) 的数据：\(1≤N≤2×10^5；1≤a[i]≤10^9\)；

提示

序列元素值成单峰：指将序列看成首尾相接的环形，再从某处断开成序列，之后序列元素以某下标 \(i\) 为最大值，下标 \(i\) 左边将呈现不减，下标 \(i\) 右边呈现不增。例如：\(6~9~8~7~7~3~1~4\)

序列元素值成双峰：指将序列看成首尾相接的环形，再从某处断开成序列，序列成两个完整单峰拼接形式。例如：\(4~5~5~7~8~8~6~3~2~3~7~9~6~2~3\)

来源

地址：\(zloj,J2021\)域
作者：\(jialiang2509\)