2193: D. 最大逆序对和(语法周赛 Round 4)

内存限制：256 MB 时间限制：1.000 S
评测方式：文本比较 命题人：
提交：4 解决：3

题目描述

33DAI 拿到了 n 个数互不相等的数，第 i 个数为 a_i。

如果两个位置 i,j，满足 i\lt j 并且 a_i > a_j，那么我们说 (a_i,a_j) 是一对逆序对。

请你找到所有逆序对中，和最大的一对，输出“和最大的逆序对”的和。（题目保证至少存在一对逆序对）。

输入

第一行一个整数 n。

接下来一行 n 个整数，a_1 \sim a_n。


输出

一行一个整数，为最大的和。

样例输入 复制 

5
3 4 5 1 2

样例输出 复制 

7

提示

5
3 4 5 1 2 
7

样例解释

和最大的逆序对为 5,2

数据规模与约定

对于 100\% 的数据，1 \le n \le 10^5，1\le a_i\le 10^9。

  • 子任务 1（30 分）：保证 a_i\gt a_{i+1}
  • 子任务 2（30 分）：保证 1\le n\le 5000
  • 子任务 3（30 分）：没有特殊限制

来源/分类

提交提交记录统计露一手!