题目描述

对序列[1, 2, 3, ... ,n]打乱后，得到序列A[1..n]。 令min(i, j)表示A[i], A[i + 1], ..., A[j]中的最小值。

给出下列伪代码，试求ans的值。

ans = 0;
for(int i = 1;i <= n; i++)
    for(int j = i;j <= n; j++)
        ans += min(i, j);

输入格式

第一行一个整数$n$，表示序列长度。

第二行$n$个整数，依次表示这$n$个数字。保证$[1, n]$中每个数字各出现一次。

输出格式

一行一个整数，表示待求解的ans的值。

3
1 3 2

10

样例解释

• [1] 最小值1
• [1, 3] 最小值1
• [1, 3, 2] 最小值1
• [3] 最小值3
• [3, 2] 最小值2
• [2] 最小值2

所以ans = 10。

数据规模与约定

共10个测试点，每个测试点10分。

大样例

大样例下载