#A0206. 最大逆序对和

最大逆序对和

题目描述

33DAI 拿到了 nn 个数互不相等的数,第 ii 个数为 aia_i

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

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

输入格式

第一行一个整数 nn

接下来一行 nn 个整数,a1ana_1 \sim a_n

输出格式

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

5
3 4 5 1 2 
7

样例解释

和最大的逆序对为 5,25,2

数据规模与约定

对于 100%100\% 的数据,1n1051 \le n \le 10^51ai1091\le a_i\le 10^9

  • 子任务 1(30 分):保证 ai>ai+1a_i\gt a_{i+1}
  • 子任务 2(30 分):保证 1n50001\le n\le 5000
  • 子任务 3(30 分):没有特殊限制