MATHS

【题目背景】

HS 不想说话。

【题目描述】

HS 给定长度为 $n$ 的数组 $a$，HS 会从中选出任意多个数，但是他是一个单身狗，不想选出两个相邻的数

HS 喜欢研究最大值与最小值，所以他知道怎样才能使选出的数中最大值加上最小值再加上选的数的个数最大。

如果你解决的这个问题，HS 会很开心并什么也不做。

【输入格式】

第一行一个整数 $n$，表示 $a$ 数组的长度。

第二行 $n$ 个整数，第 $i$ 个数表示 $a_i$。

【输出格式】

一个整数，表示最大值加最小值加所选元素个数最大值。

【样例输入1】

3
5 4 5

【样例输出1】

12

【样例输入2】

10
17 89 92 42 29 41 92 14 70 45

【样例输出2】

186

【样例说明1】

选第 $1,3$ 个数最优，答案为 $5 + 5 + 2 = 12$。

大洋里

【数据规模与约定】

对于 $5\%$ 的数据，有 $n \le 20$。

对于 $30\%$ 的数据，有 $n \le 200$。

对于 $50\%$ 的数据，有 $n \le 5000$。

对于 $80\%$ 的数据，有 $n \le 5\times 10^4$。

对于 $100\%$ 的数据，有 $n \le 2\times 10^5 , \ a_i \le 10^9$。

【来源】

//codeforces.com/contest/2018/problem/D