配点 : 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