题目描述

输入格式

第一行是一个正整数 N（2≤N≤100），表示游戏项目的数量。 第二行是 N+1 个用空格隔开的正整数，所有的数均不超过 1000。第 i 个数为第 i 个游戏项目的开始积分值（1≤i≤N），第 i 个游戏项目的结束积分值等于第 i+1 个游戏项目的开始积分值。

输出格式

一个正整数 E（E≤2.1×10⁹），为一个最优传递顺序所产生的总欢乐值。

样例

样例 1

输入 # 1

4
2 3 5 10 2

输出 # 1

710