AT_past202107_h 折れ線グラフ

[problemUrl]: https://atcoder.jp/contests/past202107-open/tasks/past202107_h 高橋君は、折れ線グラフを描く次のような宿題を先生から与えられました。 1. $ N $ 個の非負整数 $ A_1,\ A_2,\ \ldots,\ A_N $ が与えられる。ただし、$ A_1\ =\ A_N\ =\ 0 $ が成り立つ。 2. $ i\ =\ 1,\ 2,\ \ldots,\ N $ について、二次元平面上の座標 $ (i,\ A_i) $ に点 $ P_i $ を打つ。 3. $ i\ =\ 1,\ 2,\ \ldots,\ N-1 $ について、点 $ P_i $ と点 $ P_{i+1} $ を結ぶ線分を描く。 高橋君は宿題を早く済ませたいので、$ A_1,\ A_2,\ \ldots,\ A_N $ の値をこっそり変更して、 描く線分の長さの総和を小さくしようと思います。 しかし、こっそり値を変更したことを先生に気づかれないためには、 $ A_1,\ A_2,\ \ldots,\ A_N $ の変更後の値をそれぞれ $ B_1,\ B_2,\ \ldots,\ B_N $ とするとき、 以下の条件をすべて満たす必要があります。 - $ B_1,\ B_2,\ \ldots,\ B_N $ はすべて非負整数である。 - $ A_1 $ と $ A_N $ の値は変更してはならない。すなわち、$ B_1\ =\ B_N\ =\ 0 $ が成り立つ。 - $ \sum_{i=1}^{N}\ A_i\ =\ \sum_{i=1}^{N}\ B_i $ 高橋君が先生に気づかれないように $ A_1,\ A_2,\ \ldots,\ A_N $ の値を適切に変更するとき、 高橋君が描く線分の長さの総和の最小値を求めてください。

入力は以下の形式で標準入力から与えられる。 > $ N $ $ A_1 $ $ A_2 $ $ \ldots $ $ A_N $

答えを出力せよ。 想定解答との絶対誤差または相対誤差が $ 10^{-5} $ 以下であれば正解として扱われる。

### 注意 この問題に対する言及は、2021/7/17 18:00 JST まで禁止されています。言及がなされた場合、賠償が請求される可能性があります。 試験後に総合得点や認定級を公表するのは構いませんが、どの問題が解けたかなどの情報は発信しないようにお願いします。 ### 制約 - $ 2\ \leq\ N\ \leq\ 100 $ - $ 0\ \leq\ A_i\ \leq\ 100 $ - $ A_1\ =\ A_N\ =\ 0 $ - $ \sum_{i=1}^N\ A_i\ \leq\ 100 $ - 入力はすべて整数である。 ### Sample Explanation 1 高橋君は、$ A_2 $ を $ 1 $ に、$ A_3 $ を $ 2 $ に変更することで、線分の長さの総和を最小にできます。