#P13833. [cf20117exhibition]Increment and Swap

    ID: 13034 传统题 1000ms 256MiB 尝试: 1 已通过: 1 难度: 8 上传者: 标签>CF2500提高+/省选-懒标记线段树离散化有限候选集缩减

[cf20117exhibition]Increment and Swap

题目描述

有一个长度为 NN 的数列 AA。

对于该数列,你可以进行以下两种操作:

  • 交换相邻的两个元素。
  • 任意选择一个元素,将它的值增加 11。

你可以多次执行上述操作,求将数列 AA 变为广义单调不减序列所需的最少操作次数。

输入格式

输入以以下格式从标准输入读入。

NN A1A_1 A2A_2 …… ANA_N

输出格式

输出将数列 AA 变为广义单调不减序列所需的最小操作次数。

输入输出样例 #1

输入 #1

5
4
1
8
8
7

输出 #1

2

输入输出样例 #2

输入 #2

20
8
2
9
7
4
6
7
9
7
4
7
4
4
3
6
2
3
4
4
9

输出 #2

62

说明/提示

限制条件

  • 1≤N≤2000001 \leq N \leq 200000
  • 1≤Ai≤1091 \leq A_i \leq 10^9
  • AiA_i 为整数。

样例解释 1

可以通过如下两步操作将 AA 变为单调不减序列:

  • 初始时 A={4,1,8,8,7}A = \{4, 1, 8, 8, 7\}。
  • 首先交换前两个元素,得到 A={1,4,8,8,7}A = \{1, 4, 8, 8, 7\}。
  • 然后将最后一个元素增加 11,得到 A={1,4,8,8,8}A = \{1, 4, 8, 8, 8\}。

由 ChatGPT 5 翻译