C1766 [国庆欢乐赛]高速公路

内存限制:256 MB 时间限制:500 ms

题目描述

女朋友坐飞机到南京来陪鸡尾酒实习,航班马上就要抵达了,于是鸡尾酒刚下班就开车(三轮车)火速赶往机场。机场高速是公司到机场的必经之路,所以鸡尾酒在几天前就对机场高速做了研究。

机场高速分为 $n$ 段,第 $i$ 段的限速为 $a_i$。在每一段中,可以认为鸡尾酒的车速是保持不变的,在第 $i$ 段时鸡尾酒的车速是 $v_i$。每一段只允许汽车的速度比上一段的速度 +-10 或维持不变,也就是说,对于所有满足 $1 \le i < n$ 的正整数 $i$,$v_{i+1}$ 只会有 $v_i - 10, v_i, v_i + 10$ 三种可能。

鸡尾酒定义这段路途的快速值为每一段的速度之和 (也就是 $\sum\limits_{i=1}^{n} v_i$)。

鸡尾酒希望这段路途的快速值尽可能的大,但是他最多只能超速 $1$ 次 (也就是至多存在一个$i$ 使得 $v_i > a_i$ ),请问他可以达到最大的快速值是多少。

输入格式

第一行给出一个$n$,代表机场高速的段数。接下来一行给出 $n$ 个正整数,分别代表每一段的限速 $a_i$。

  • $2 \le n \le 10^5$
  • $10 \le a_i \le 10^9, a_i$ 是 $10$ 的整数倍

输出

输出一行一个整数表示这段路途鸡尾酒的最大快速值

样例

样例输入 1

3 40 30 20

样例输出 1

110

提示