题目描述

石老板的祖先（石先锋）曾经是秦始皇手下的大将，当年帮秦始皇埋了一笔宝藏。

石老板费经千辛万苦寻找宝藏所在地，但是门口有机关需要破解，只见上面有如下Python代码：

def calculate_ans(permutation):
    n = len(permutation)
    ans = 0
    for i in range(n):
        for j in range(i, n):
            min_index = i
            max_index = i
            for k in range(i, j + 1):
                if permutation[k] < permutation[min_index]:
                    min_index = k
                if permutation[k] > permutation[max_index]:
                    max_index = k
            ans += abs(min_index - max_index)
    return ans

已知该函数的参数permutation是一个list，内容是 $1\sim n$ 的排列。

石老板发现该函数时间复杂度是 $O(n^3)$ 的，似乎不太聪明的样子。就在这时，石老板收到了一条短信，是秦始皇发来的，上面写着让石老板翻译成C++ 代码，并优化效率。

请你帮助石老板完成这个任务。

输入格式

第一行一个整数 $n$，表示排列大小。

第二行 $n$ 个正整数 $a_i$，用空格分隔。

输出格式

一个整数，表示最终答案。

样例输入

7
4 5 7 1 3 2 6

样例输出

24

数据范围

对于 $10\%$ 的数据，$n\le 200$；

对于 $40\%$ 的数据，$n\le 2000$;

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

保证 $a_i$ 是一个 $1\sim n$ 的排列。