AT_abc435_f [ABC435F] Cat exercise

$ N $ 個のキャットタワーが左右一列に並んでおり、左から $ i $ 番目 $ (1\leq i\leq N) $ のタワーの高さは $ P_i $ です。 ここで、 $ (P_1,P_2,\ldots,P_N) $ は $ (1,2,\ldots,N) $ の並び替えとなっています。 また、左から $ i $ 番目のタワーと $ j $ 番目のタワーの間の距離を $ \lvert i-j\rvert $ で定義します。 猫が一匹おり、最初、高さ $ N $ のキャットタワーの上にいます。 高橋君はタワーを一つ選んで撤去することを繰り返すことで、この猫を運動させたいです。 高橋君がタワーを撤去するとき、猫は以下のように移動します。 - 撤去するタワーの上に猫がいない場合、猫は移動しません。 - 撤去するタワーの上に猫がおり、かつそのタワーと左右に隣接するタワーのうち少なくとも一方が存在するとき、撤去されるタワーからスタートして隣接するタワーへの移動を繰り返して到達できるタワーのうち、撤去されるタワーを除いて最も高いタワーに猫が移動します。 このとき、移動前と移動後のタワーの間の距離だけ移動が発生します（移動前後および途中のタワーの高さは関係しません）。 - 撤去するタワーの上に猫がおり、かつそのタワーと左右に隣接するタワーが存在しないとき、猫は高橋君の腕の中に飛び込み、運動はここで終了となります。このときには移動は発生しません。 ここで、撤去したタワーの間は詰めることはありません。 すなわち、最初の時点で左から $ i $ 番目のタワーと隣接しているタワーは（存在すれば）左から $ (i-1) $ 番目と $ (i+1) $ 番目のタワーのみであり、 その後 **他のタワーの撤去によって新しく他のタワーと隣接するようになることはありません**。 運動が終了するまでの猫の移動距離の合計としてあり得る最大の値を求めてください。

入力は以下の形式で標準入力から与えられる。 > $ N $ $ P_1 $ $ P_2 $ $ \ldots $ $ P_N $

運動が終了するまでの猫の移動距離の合計としてあり得る最大の値を出力せよ。

### Sample Explanation 1 最初、キャットタワーの高さは左から順に $ 5,3,4,1,2 $ です。 以下、左から $ i $ 番目 $ (1\leq i\leq 5) $ のキャットタワーをタワー $ i $ と呼びます。 最初、猫はタワー $ 1 $ （高さ $ 5 $ ）にいます。 高橋君がタワー $ 1,2,3,5,4 $ の順に取り除くと猫は次のように移動します。 - 高橋君がタワー $ 1 $ を取り除く。タワー $ 1 $ から隣接するタワーへの移動のみで移動できるタワーは（タワー $ 1 $ を除いて）タワー $ 2,3,4,5 $ である。猫はこのうち最も高いタワー $ 3 $ （高さ $ 4 $ ）に移動する。 - 高橋君がタワー $ 2 $ を取り除く。猫は移動しない。 - 高橋君がタワー $ 3 $ を取り除く。タワー $ 3 $ から隣接するタワーへの移動のみで移動できるタワーは（タワー $ 3 $ を除いて）タワー $ 4,5 $ である。猫はこのうち最も高いタワー $ 5 $ （高さ $ 2 $ ）に移動する。 - 高橋君がタワー $ 5 $ を取り除く。タワー $ 5 $ から隣接するタワーへの移動のみで移動できるタワーは（タワー $ 5 $ を除いて）タワー $ 4 $ のみである。猫はタワー $ 4 $ （高さ $ 1 $ ）に移動する。 - 高橋君がタワー $ 4 $ を取り除く。猫は高橋君の腕に飛び込み、運動は終了する。 このとき、猫の移動距離の合計は $ \lvert 1-3\rvert+\lvert 3-5\rvert+\lvert 5-4\rvert=5 $ となります。 移動距離の合計を $ 6 $ 以上にする取り除き方は存在しないため、 $ 5 $ を出力します。 ### Sample Explanation 2 最初、キャットタワーの高さは左から順に $ 1,3,2 $ です。 以下、左から $ i $ 番目 $ (1\leq i\leq 3) $ のキャットタワーをタワー $ i $ と呼びます。 最初、猫はタワー $ 2 $ （高さ $ 3 $ ）にいます。 高橋君がタワー $ 2,3 $ の順に取り除くと猫は次のように移動します。 - 高橋君がタワー $ 2 $ を取り除く。タワー $ 2 $ から隣接するタワーへの移動のみで移動できるタワーは（タワー $ 2 $ を除いて）タワー $ 1,3 $ である。猫はこのうち最も高いタワー $ 3 $ （高さ $ 2 $ ）に移動する。 - 高橋君がタワー $ 3 $ を取り除く。猫は高橋君の腕に飛び込み、運動は終了する。 このとき、猫の移動距離の合計は $ \lvert 2-3\rvert=1 $ となり、このときが最大です。 タワー $ 2 $ を取り除いた後も、タワー $ 1 $ とタワー $ 3 $ は隣接しているとみなされないことに注意してください。 ### Constraints - $ 1\leq N\leq 2\times 10^5 $ - $ (P_1,P_2,\ldots, P_N) $ は $ (1,2,\ldots,N) $ の並び替えである。 - 入力はすべて整数