问题2551--这好像是一道签到题?

2551: 这好像是一道签到题?

时间限制: 1 Sec  内存限制: 128 MB
提交: 13  解决: 3
[提交] [状态] [讨论版] [命题人:]

题目描述

你将得到一个长度为 n 的数组 a ,最初第 i 个位置的值为 ai

为此,你可以进行以下操作

- 选择任意子区间,将这个子区间的所有元素减一(前提条件:子区间每个元素相等)

举例: a=[2,6,6,7,7,7]

- 选择子区间  [2,3] ,两次操作,a=[2,4,4,7,7,7]
- 选择子区间  [4,5] ,一次操作,a=[2,6,6,6,6,7]
- 选择子区间  [3,4] 是不合法的,因为子区间的元素存在不相等。



定义:


符号解释:“西格玛”是希腊字母,符号是 ,英文译音是 Sigma , 表示数学中的求和号,是数学中常用的符号,主要用于求多项数的和。





进行一定次数操作后,获得新的数组 a ,必须保证任意 f(l,r) 能被 r-l+1 整除,并且 f(l,r)>0

杨会喜欢极致的操作,要求新的数组 a 的元素之和在最小的情况下,最小化操作数。

(题目保证:在约束条件上,一定可以构造新的数组 a 。)


输入

第一行包含一个整数 n1n106)。

第二行包含 n 个整数 a1 ,a2 ,…,an ( i+1 ≤ ai 109—数组 a 的元素。

输出

输出一个整数  a ,表示最小的操作数。

样例输入

4
4 8 6 7

样例输出

7

来源/分类


[提交] [状态]