Time Limit: 2 sec / Memory Limit: 256 MB
問題文
かがみずくんはめちゃくちゃ太っています.そのため,近頃,身体に良さそうなことをいろいろ行っています.
かがみずくんは,日光浴のため屋上へ行きたいのですが,その体重のせいで屋上へ行くために必要なはしごを壊してしまいました.
仕方ないので何か代替手段を用いて屋上に行かなければならないのですが,室内には無造作に積まれたコンクリートブロックしかありません.そこで,賢いかがみずくんは,コンクリートブロックを階段状に積み,それらを用いて屋上に行こうとしました.
状況を整理しましょう.今,屋上は高さ N+1 の位置にあります.そして,それぞれ高さ 1 のコンクリートブロックが,合計ちょうど \frac{N(N+1)}{2} (=1+2+...+N)個,N 箇所の位置に無造作に積まれ,ブロック山になっています.
ブロック山は一直線に並んでいます.かがみずくんは高さ 1 の段差しか登ることができないので,屋上から遠いほうから近いほうへ 1 段, 2 段, ..., N 段と階段をつくりたいです.
かがみずくんが,あるブロック山の一番上にあるブロックを,別の位置のブロック山の一番上に置くことを,一回の操作と定義しましょう.
例えば,今 N=4 として,最初ブロック山が遠い方から近い方に「3 段,1 段,5 段,1 段」というふうに段積まれているとしましょう.これらを階段にするために,下図のような操作がひとつの例として考えられます.
あなたの仕事は,無造作に置かれた N 箇所のブロック山の初期状態が与えられるので,かがみずくんが屋上へ行くための階段を構築するのに最低で何回の操作をする必要があるかを数えることです.
課題
N 要素の非負整数列 A が与えられる.A の要素の総和は \frac{N(N+1)}{2} (=1+2+...+N) である.
いま,1 回の操作で A の好きな要素の値を 1 だけ減らし,かわりに他の好きな要素の値を 1 だけ増やすことができる.
i = 1, ..., N に対し A_i = i が成り立つような状態にするために最低限必要な操作の回数を求めよ.
制約
すべての入力データは以下の制約を満たす.
- 1 ≦ N ≦ 100.
入力
N A_1 A_2 : A_N
出力
最低限必要な操作の回数を 1 行に出力せよ.
入力例 1
3 3 2 1
出力例 1
2
A_1 を減らして A_3 を増やす操作を 2 回行えばよい.
入力例 2
4 3 1 5 1
出力例 2
4
入力例 3
5 7 8 0 0 0
出力例 3
12
Problem: kagamiz
Tester: kyuridenamida, japlj