B - Increment and Rotate
Editorial
/
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 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