問題一覧 > 通常問題

No.1294 マウンテン数列

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 46
作問者 : 沙耶花 / テスター : tko919
10 ProblemId : 4473 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2020-10-04 20:56:50

問題文

ある単調増加な数列Xと単調減少な数列Yをこの順に連結することで得られる数列をマウンテン数列と呼ぶことにします.

また, 長さ2以上のマウンテン数列{x1,x2,...,xn}に対し,
|x1−x2|,|x2−x3|,...,|xn−1−xn|のうち最大の値をその数列の危険度と呼ぶことにします.
例えば, 数列{3,7,9,4}や{1,2,4}はどちらもマウンテン数列であり, 危険度は順に5, 2です.

どの要素も相異なる正整数列{A1,A2,...,AN}が与えられます.
これを並び替えて得られるマウンテン数列すべてに対しその危険度を求め,
総和をmod998244353で出力してください.

入力

N
A1 A2 ... AN

  • 2≤N≤2500
  • 1≤A1<A2<...<AN≤2500
  • 入力はすべて整数

出力

答えを出力してください.
最後に改行してください.

サンプル

サンプル1
入力
3
1 2 4
出力
10

並べ替えて得られるマウンテン数列は{1,2,4},{1,4,2},{2,4,1},{4,2,1}の4通りです.
これらの危険度は順に2,3,3,2なので, この合計である10を出力します.

サンプル2
入力
4
3 4 7 9
出力
38

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。