小 C 有一个元素两两不同的长度为 n 的序列 A，但是这个序列可能是无序的。

小 C 不喜欢无序的序列，他现在可以做以下操作任意次：

• 任意选择一个区间 [l,r]，花费 r-l 的代价将区间 [l,r] 中的数从小到大排序。

小 C 想用最小的代价和让序列 A 有序（从小到大），但他不仅仅只满足于求出让序列 A 有序的最小代价。

小 C 设 f_{l,r} 表示在只考虑序列 A 的区间 [l,r] 的前提下，让子序列 [A_l,A_{l+1},...,A_r] 有序的最小代价和。

他想请你求出 \sum_{i=1}^n \sum_{j=i}^n f_{i,j} 的值。

输入的第一行包含一个整数 n。

接下来一行包含 n 个整数，第 i 个整数表示 A_i。

共一行，输出一个整数。

数据规模与约定

• 对于 20\% 的数据，保证 n\le 5。
• 对于 40\% 的数据，保证 n\le 16。
• 对于 60\% 的数据，保证 n\le 500。
• 对于 80\% 的数据，保证 n\le 5000。
• 对于 100\% 的数据，保证 1\le n\le 3\times 10^5，1\le A_i\le 10^9，保证序列 A 中元素两两不同。

样例 1 解释

f_{1,1}=f_{2,2}=f_{3,3}=0。

f_{1,2}=0,f_{2,3}=1。

f_{1,3}=1。

CSP-J模拟赛