传统题 2000ms 256MiB

排序

该比赛已结束,您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

小 C 有一个元素两两不同的长度为 nn 的序列 AA,但是这个序列可能是无序的。

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

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

小 C 想用最小的代价和让序列 AA 有序(从小到大),但他不仅仅只满足于求出让序列 AA 有序的最小代价。

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

他想请你求出

i=1nj=infi,j\sum_{i=1}^n \sum_{j=i}^n f_{i,j}

的值。

输入格式

输入的第一行包含一个整数 nn

接下来一行包含 nn 个整数,第 ii 个整数表示 AiA_i

输出格式

共一行,输出一个整数。

样例 1 输入

3
3 10 6

样例 1 输出

2

样例 1 解释

f1,1=f2,2=f3,3=0f_{1,1}=f_{2,2}=f_{3,3}=0

f1,2=0,f2,3=1f_{1,2}=0,f_{2,3}=1

f1,3=1f_{1,3}=1

样例 2 输入

5
9 8 2 4 6

样例 2 输出

16

其余样例见下发文件

数据规模与约定

  • 对于 20%20\% 的数据,保证 n5n\le 5
  • 对于 40%40\% 的数据,保证 n16n\le 16
  • 对于 60%60\% 的数据,保证 n500n\le 500
  • 对于 80%80\% 的数据,保证 n5000n\le 5000
  • 对于 100%100\% 的数据,保证 1n3×1051\le n\le 3\times 10^51Ai1091\le A_i\le 10^9,保证序列 AA 中元素两两不同。

[JKFZ_S-]2025-3月测

未参加
状态
已结束
规则
OI
题目
4
开始于
2025-3-17 18:30
结束于
2025-3-19 22:00
持续时间
3 小时
主持人
参赛人数
15