活动结束后，老师要给排成一队的同学发鼓励徽章。一共有 n 名同学，从左到右第 i 名同学的表现分是 a_i。每名同学至少要得到 1 枚徽章。为了让同学们觉得公平，还要满足：如果某名同学的表现分比左边相邻同学高，那么他得到的徽章数必须比左边相邻同学多；如果某名同学的表现分比右边相邻同学高，那么他得到的徽章数必须比右边相邻同学多。表现分相同的相邻同学之间没有额外要求。请计算老师最少一共需要准备多少枚徽章。

第一行一个整数 n。第二行 n 个整数 a_1, a_2, ..., a_n，表示每名同学的表现分。

一行一个整数，表示最少徽章总数。

【数据范围】
30 分：1 ≤ n ≤ 8，1 ≤ a_i ≤ 10
60 分：1 ≤ n ≤ 5000
100 分：1 ≤ n ≤ 200000，1 ≤ a_i ≤ 10^9
【样例说明】
一种最少发法为：1 2 1 1 2 1 2。可以检查每一对相邻同学，表现分更高的一边拿到的徽章也更多。总数是 1 + 2 + 1 + 1 + 2 + 1 + 2 = 10。

数组