問題文

長さ 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
• 入力される値はすべて整数である

入力例 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