登顶
题号：NC208150
时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld

题目描述

在Madeline和Badeline合作之后，登顶变得越来越得心应手了。她们在一路上收集到了个草莓，收集到的第个草莓的价值是v_i。Madeline想要知道所有区间的草莓价值最大值乘以草莓价值最小值之和是多少，即是多少。

但以Madeline的能力无法知道，你能帮帮她吗？

输入描述:

第一行输入一个整数，表示一共收集到个草莓。

第二行输入个整数，第个数表示第个草莓的价值是v_i。

输出描述:

输出一个整数表示答案。
示例1

输入

复制 
2
1 2

输出

复制 
7

说明

区间{}[1,1]的最大值是{}1，最小值是{}1。
区间{}[1,2]的最大值是{}2，最小值是{}1。
区间{}[2,2]的最大值是{}2，最小值是{}2。
故答案为1\cdot{1}+2\cdot{1}+2\cdot{2}=7

备注:

输入的数据量很大，C++选手建议使用scanf代替cin，Java选手建议自己写一个输入流代替Scanner。