题目描述

给定一个长度为 $n$ 的序列 $a_1, a_2, . . . , a_n$，对于序列中的每一个元素 $a_i(1 ≤ i ≤ n)$，

定义其“影响度”为:

• 在 $a_i$ 的前面(即 $a_1$ 到 $a_{i−1}$ 中)，找到第一个严格大于 $a_i$ 的元素 $a_j$ $(j < i)$，则 $a_i$ 的影响度为 $i − j$;

• 如果 $a_i$ 前面没有严格大于它的元素，则其影响度为 $0$。 要求计算所有元素的影响度之和。

输入格式

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

第二行:$n$ 个整数 $a_1, a_2, . . . , a_n$，表示序列。

输出格式

一个整数，表示所有元素的影响度之和。

样例 1 输入

6
4 3 2 1 6 5 

样例 1 输出

7

样例 1 解释

每个元素的影响度分别为 $0 1 2 3 0 1$。

数据范围

• 对于 $30\%$ 的数据，$n ≤ 1000$。

• 对于 $100\%$ 的数据，$1≤n≤10^6$，$1≤a_i ≤10^6$。