题目描述

给一定一个数组，每个位置的美好值是离该位置最近的且下标小于该位置，值小于等于该值的值，若没有则为0。求所有位置的美好值总和。

输入描述

第一行一个整数$n$，表示数组长度。$(1 \leq n \leq 10^5)$

接一行下来$n$个整数，表示该数组。$(1 \leq a[i] \leq 10^5)$

输出描述

输出一个整数，表示美好值的总和

样例

输入

5
2 3 4 1 5

输出

6

说明

0号位置前面没有值，美好值为0

1号位置前面最近小于等于的值为2，美好值为2

2号位置前面最近小于等于的值为3，美好值为3

3号位置前面没有小于等于该值的数，美好值为0

4号位置前面最近小于等于的值为1，美好值为1

总的美好值为$2+3+1=6$