← 返回题目列表

AtCoder · jsc2022_final_b

B. 增量和旋转

中文机器翻译题面 查看原题

配点 : 600 点

問題文

长度 小于或等于 N 整数序列 给出 A=(A_1,A_2,\cdots,A_N) 。

您有以下内容 2 以任何顺序和任意次数执行任何类型的操作 ( 可以重复0 次)。

  • 操作 1: A 的第一个元素 添加 1 。换句话说, 将A_1:=A_1+1 。
  • 操作 2: A 的第一个元素移动到末尾。换句话说,A:=(A_2,A_3,\cdots,A_N,A_1) 。

你的目标是A 大致单调递增(A_1 \leq A_2 \leq \cdots \leq A_N)。 找出实现目标所需的最少操作次数。

制約

  • 2 \leq N \leq 2 \times 10^5
  • 1 \leq A_i \leq 10^9
  • 所有输入值均为整数

入力

输入是按以下格式从标准输入给出的。

N
A_1 A_2 \cdots A_N

出力

打印答案。


入力例 1

4
2 4 1 3

出力例 1

3

只需按如下操作即可。 执行

  • 操作 1 。 它变成A=(3,4,1,3) 。
  • 操作 2 。 它变成A=(4,1,3,3) 。
  • 操作 2 。 它变成A=(1,3,3,4) 。

入力例 2

20
786820955 250480341 710671230 946667801 19271059 404902145 251317818 22712439 520643153 344670307 274195604 561032101 140039457 543856068 521915711 857077284 499774361 419370025 744280521 249168130

出力例 2

3774454944